Pagini recente » Borderou de evaluare (job #2424207) | Monitorul de evaluare | Borderou de evaluare (job #3332574) | Monitorul de evaluare | Cod sursa (job #3301079)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct P {
long double x, y;
} a[150005];
int n, stk[150005], top, ref;
long double bx, by = 1e18;
bool cmp(const P &p1, const P &p2) {
return p1.x * p2.y >= p2.x * p1.y;
}
bool ok(P p1, P p2, P p3) {
long double d = p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);
return d > 0;
}
int main() {
fin >> n;
for (int i = 1; i <= n; i++) {
fin >> a[i].x >> a[i].y;
if (a[i].y < by || (a[i].y == by && a[i].x < bx)) {
bx = a[i].x;
by = a[i].y;
ref = i;
}
}
for (int i = 1; i <= n; i++) {
a[i].x -= bx;
a[i].y -= by;
}
swap(a[1], a[ref]);
sort(a + 2, a + n + 1, cmp);
stk[1] = 1;
stk[2] = 2;
top = 2;
for (int i = 3; i <= n; i++) {
while (top >= 2 && !ok(a[stk[top - 1]], a[stk[top]], a[i])) top--;
stk[++top] = i;
}
fout << top << '\n';
fout << fixed << setprecision(10);
for (int i = 1; i <= top; i++) {
fout << a[stk[i]].x + bx << ' ' << a[stk[i]].y + by << '\n';
}
return 0;
}