Pagini recente » Cod sursa (job #931964) | Cod sursa (job #1673237)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define inf 1999999999
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{
double x, y;
double panta; // panta dreptei formate de punctul v[i] si colt
}v[120005], colt;
int stiva[120005], vf, n, i, poz;
bool cmp(punct a, punct b)
{
return a.panta < b.panta;
}
bool convex(punct a, punct b, punct c)
{
return ((a.x-c.x)*(b.y-a.y) + (a.x-b.x)*(a.y-c.y)) > 0;
}
int main()
{
colt.x = colt.y = inf;
f >> n;
for (i = 1; i <= n; i++)
{
f >> v[i].x >> v[i].y;
if (v[i].x < colt.x || (v[i].y < colt.y && v[i].x == colt.x))
colt = v[i], poz = i;
}
swap(v[poz], v[1]);
for (i = 2; i <= n; i++)
v[i].panta = (v[i].y - colt.y)/(v[i].x - colt.x);
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 > 2)
vf--;
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;
}