Pagini recente » Cod sursa (job #706085) | Cod sursa (job #1214040) | Cod sursa (job #1116568) | Cod sursa (job #2683500) | Cod sursa (job #1857976)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct {
double x, y, panta;
};
punct v[120005];
int colt;
int n, i;
int stiva[120005], vf;
bool cmp(punct a, punct b) {
return a.panta < b.panta;
}
bool convex(punct a, punct b, punct c) {
double det = (a.x*b.y+b.x*c.y+a.y*c.x-c.x*b.y-a.x*c.y-b.x*a.y);
return det > 0;
}
int main() {
f >> n;
colt = 1;
for (i = 1; i <= n; i++) {
f >> v[i].x >> v[i].y;
if (v[colt].x > v[i].x || (v[colt].x ==v[i].x && v[i].y < v[colt].y))
colt = i;
}
swap(v[1], v[colt]);
for (i = 2; i <= n; i++)
v[i].panta = (v[i].y-v[1].y)/(v[i].x-v[1].x);
sort(v+2, v+n+1, cmp);
stiva[1] = 1, stiva[2] = 2, vf = 2;
for (i = 3; i <= n; i++) {
if (!convex(v[stiva[vf-1]], v[stiva[vf]], v[i]) && vf > 2)
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';
return 0;
}