Pagini recente » Cod sursa (job #2588097) | Cod sursa (job #1049197) | Cod sursa (job #2716192) | Clasament Runda 1 | Cod sursa (job #2084261)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int nmax = 120005;
struct punct {
double x, y;
}v[nmax], pmin;
const double EPS = 1e-12;
int n, i, j, poz;
int stiva[nmax], vf;
bool cmp(punct a, punct b) {
return (b.y-pmin.y)*(a.x-pmin.x) > (a.y-pmin.y)*(b.x-pmin.x);
}
double det(punct a, punct b, punct c) {
return a.x*b.y+b.x*c.y+c.x*a.y - c.x*b.y-b.x*a.y-a.x*c.y;
}
bool convex(punct a, punct b, punct c) {
return (det(a, b, c) > EPS);
}
int main() {
f >> n;
pmin.x = pmin.y = 2e9;
for (i = 1; i <= n; i++) {
f >> v[i].x >> v[i].y;
if (v[i].x < pmin.x || (v[i].x == pmin.x && v[i].y < pmin.y))
pmin = v[i], poz = i;
}
swap(v[1], v[poz]);
sort(v+2, v+n+1, cmp);
stiva[1] = 1, stiva[2] = 2;
vf = 2;
for (i = 3; i <= n; i++) {
while (convex(v[stiva[vf-1]],v[stiva[vf]],v[i]) == 0 && vf > 1)
vf--;
stiva[++vf] = i;
}
g << vf << '\n';
for (i = 1; i <= vf; i++)
g << fixed << setprecision(6) << v[stiva[i]].x << ' ' << v[stiva[i]].y << '\n';
}