|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
struct point {
ll x, y;
ll p = 0, q = 0;
};
bool cmp2(point& a, point& b) {
if (1LL * a.p * b.q != 1LL * a.q * b.p) return 1LL * a.q * b.p < 1LL * a.p * b.q;
if (a.x != b.x) return a.x > b.x;
return a.y < b.y;
}
bool cmp(point& a, point& b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
ll ccw(point& a, point& b, point& c) {
return 1LL * (b.x - a.x) * (c.y - a.y) - 1LL * (b.y - a.y) * (c.x - a.x);
}
int N, i, x, y;
point arr[100000];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
for (cin >> N; i < N; i++) {
cin >> arr[i].x >> arr[i].y;
char ch;
cin >> ch;
if (ch == 'N')N--, i--;
}
sort(arr, arr + N, cmp);
for (int i = 1; i < N; i++) {
arr[i].p = arr[i].x - arr[0].x;
arr[i].q = arr[i].y - arr[0].y;
}
sort(arr + 1, arr + N, cmp2);
stack<int> s;
int next = 2;
s.push(0);
s.push(1);
while (next < N) {
while (s.size() >= 2) {
int first, second;
second = s.top();
s.pop();
first = s.top();
if (ccw(arr[first], arr[second], arr[next]) >= 0) {
s.push(second);
break;
}
}
s.push(next++);
}
vector<point> v;
while (!s.empty()) {
int idx = s.top();
s.pop();
v.push_back(arr[idx]);
}
cout << v.size() << endl;
for (int i = v.size() - 1; i >= 0; i--) {
cout << v[i].x << " " << v[i].y << "\n";
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
'algorithm' 카테고리의 다른 글
| 최대 합 경로 찾기(과제) (0) | 2020.04.29 |
|---|---|
| 의료봉사(과제) (0) | 2020.04.27 |