Pagini recente » Cod sursa (job #911299) | Cod sursa (job #1600042) | Cod sursa (job #3233854) | Cod sursa (job #2124523) | Cod sursa (job #3284356)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct Point {
double x, y;
};
int n;
Point v[120005];
Point stck[120005];
int head;
double cross_product(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool cmp(Point a, Point b) {
return cross_product(v[1], a, b) < 0;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); in.tie(nullptr);
// input
in >> n;
for(int i = 1; i <= n; i++) {
in >> v[i].x >> v[i].y;
}
// sort
int pos = 1;
for(int i = 2; i <= n; i++) {
if(v[i].x < v[pos].x || (v[i].x == v[pos].x && v[i].y < v[pos].y)) {
pos = i;
}
}
swap(v[1], v[pos]);
sort(v + 2, v + n + 1, cmp);
// convex hull
stck[1] = v[1];
stck[2] = v[2];
head = 2;
for(int i = 3; i <= n; i++) {
while(head >= 2 && cross_product(stck[head - 1], stck[head], v[i]) > 0) {
head--;
}
stck[++head] = v[i];
}
// output
out << head << '\n';
for(int i = head; i >= 1; i--) {
out << fixed << setprecision(9) << stck[i].x << ' ' << stck[i].y << '\n';
}
return 0;
}