Pagini recente » Cod sursa (job #2885154) | Cod sursa (job #820148) | Cod sursa (job #426945) | Cod sursa (job #1355944) | Cod sursa (job #3154876)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n;
struct point {
double x, y;
};
point v[120005], st[120005];
double angle(point a, point b, point c) {
return (b.y - a.y) * (c.x - a.x) - (b.x - a.x) * (c.y - a.y);
}
bool cmp(point a, point b) {
return angle(v[1], a, b) > 0;
}
int top;
int main()
{
in >> n;
int pos = 0;
for (int i = 1; i <= n; i++) {
in >> v[i].x >> v[i].y;
if (pos == 0 || (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);
top = 2;
st[1] = v[1];
st[2] = v[2];
for (int i = 3; i <= n; i++) {
while (top >= 2 && angle(st[top - 1], st[top], v[i]) < 0)
top--;
st[++top] = v[i];
}
out << top << '\n';
for (int i = top; i > 0; i--)
out << fixed << setprecision(6) << st[i].x << " " << st[i].y << '\n';
return 0;
}