Pagini recente » Cod sursa (job #2611530) | Cod sursa (job #2989785) | Cod sursa (job #370626) | Cod sursa (job #882862) | Cod sursa (job #2132205)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int nmax = 120005, f_mare = 1e9;
int n, i, poz;
struct punct {
double x, y;
} a[nmax], minim;
int stiva[nmax], vf;
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 - c.y*a.x;
}
bool cmp(const punct &a, const punct &b) {
return (a.y-minim.y)*(b.x-minim.x) < (b.y-minim.y)*(a.x-minim.x);
}
int main() {
f >> n;
minim = {f_mare, f_mare};
for (i = 1; i <= n; i++) {
f >> a[i].x >> a[i].y;
if (a[i].x < minim.x || (a[i].x == minim.x && a[i].y < minim.y))
poz = i, minim = a[i];
}
swap(a[1], a[poz]);
sort(a+2,a+n+1,cmp);
stiva[1] = 1, stiva[2] = 2;
vf = 2;
for (i = 3; i <= n; i++) {
while (vf > 2 && det(a[stiva[vf-1]], a[stiva[vf]], a[i]) <= 0) vf--;
stiva[++vf] = i;
}
g << vf << '\n';
for (i = 1; i <= vf; i++)
g << fixed << setprecision(6) << a[stiva[i]].x << ' ' << a[stiva[i]].y << '\n';
return 0;
}