Pagini recente » Borderou de evaluare (job #2696164) | Cod sursa (job #877995) | Cod sursa (job #3354486) | Borderou de evaluare (job #1863691) | Cod sursa (job #3301080)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
struct P {
long double x, y;
} a[150005];
int n, st[150005], top, pmin;
long double bx, by = 1e18;
long double cross(P a, P b, P c) {
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}
bool cmp(P a, P b) {
return a.x * b.y >= b.x * a.y;
}
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
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;
pmin = i;
}
}
for (int i = 1; i <= n; i++) {
a[i].x -= bx;
a[i].y -= by;
}
swap(a[1], a[pmin]);
sort(a + 2, a + n + 1, cmp);
st[++top] = 1;
st[++top] = 2;
for (int i = 3; i <= n; i++) {
while (top >= 2 && cross(a[st[top - 1]], a[st[top]], a[i]) <= 0) top--;
st[++top] = i;
}
fout << top << '\n';
fout << fixed << setprecision(10);
for (int i = 1; i <= top; i++) {
fout << a[st[i]].x + bx << ' ' << a[st[i]].y + by << '\n';
}
return 0;
}