Pagini recente » Cod sursa (job #3344940) | Cod sursa (job #3317045) | Borderou de evaluare (job #1394799) | Cod sursa (job #3340258) | Cod sursa (job #3345181)
#include <iostream>
#include <algorithm>
const int MAX_N = 1e5;
struct vec2 {
int x, y;
void read() {
scanf("%d %d", &x, &y);
}
};
struct Stack {
int st[MAX_N];
int sp = 0;
int len() {
return sp;
}
void push(int val) {
st[sp++] = val;
}
int pop() {
return st[--sp];
}
int first() {
return st[sp - 1];
}
int second() {
return st[sp - 2];
}
};
int n;
vec2 a[MAX_N];
void read_points() {
for (int i = 0; i < n; i++) {
a[i].read();
}
}
int find_extreme() {
int res = 0;
for (int i = 1; i < n; i++) {
if (
(a[i].y < a[res].y) ||
(a[i].y == a[res].y && a[i].x < a[res].x)
) {
res = i;
}
}
return res;
}
long long det(vec2 a, vec2 b, vec2 c) {
return (long long)(c.x - a.x) * (b.y - a.y)
- (long long)(c.y - a.y) * (b.x - a.x);
}
long long dist2(vec2 a, vec2 b) {
return (long long)(a.x - b.x) * (a.x - b.x)
+ (long long)(a.y - b.y) * (a.y - b.y);
}
void polar_sort_points() {
vec2 a0 = a[0];
std::sort(a + 1, a + n, [a0](vec2 a, vec2 b) {
long long d = det(a0, a, b);
if (d != 0) return d < 0;
else return dist2(a0, a) < dist2(a0, b);
});
}
Stack graham_scan() {
Stack st;
for (int i = 0; i < n; i++) {
while (st.len() >= 2 && det(a[st.second()], a[st.first()], a[i]) >= 0) {
st.pop();
}
st.push(i);
}
return st;
}
void print_hull(Stack st) {
printf("%d\n", st.len());
for (int i = 0; i < st.len(); i++) {
vec2 p = a[st.st[i]];
printf("%d %d\n", p.x, p.y);
}
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
read_points();
std::swap(a[0], a[find_extreme()]);
polar_sort_points();
Stack hull = graham_scan();
print_hull(hull);
}