Cod sursa(job #890396)
// infasuratoarea ma-sii
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
int n, pos, vf;
struct Punct
{
double x, y;
};
Punct a[120010], st[120010];
inline void Read()
{
ifstream f ("infasuratoare.in");
f>>n;
int i;
double x, y;
pos = 1;
for (i=1; i<=n; i++)
{
f>>x>>y;
a[i].x = x;
a[i].y = y;
if (y < a[pos].y || (y == a[pos].y && x < a[pos].x))
pos = i;
}
f.close();
}
inline double Dist(const Punct A)
{
return (A.x-a[1].x)*(A.x-a[1].x)+(A.y-a[1].y)*(A.y-a[1].y);
}
inline bool cmp (const Punct A, const Punct B)
{
//y2 - y0 / x2 - x0 < y1 - y0 / x1 - x0
//y2 - y0 * x1 - x0 < y1 - y0 * x2 - x0
double p1, p2;
p1 = (B.y - a[1].y)*(A.x - a[1].x);
p2 = (A.y - a[1].y)*(B.x - a[1].x);
if (p1 == p2) // daca au aceleasi distanta le sortez crescator dupa distanta pana la punctul din stanga-jos
return Dist(A) < Dist(B);
return p1 < p2;
}
inline double Intoarcere(const Punct A, const Punct B, const Punct C)
{
// A.x A.y 1
// B.x B.y 1
// C.x C.y 1
return A.x * B.y + B.x * C.y + A.y * C.x - B.y * C.x - A.y * B.x - A.x * C.y;
}
inline void Infasoara()
{
Punct aux;
aux = a[1];
a[1] = a[pos];
a[pos] = aux;
sort(a+2, a+n+1, cmp);
vf++;
st[vf] = a[1];
vf++;
st[vf] = a[2];
int i;
double o;
for (i = 3; i<=n; i++)
{
o = Intoarcere (st[vf-1], st[vf], a[i]);
if (o == 0.0) // puncte colineare
st[vf] = a[i];
else
if (o < 0.0) // daca face intoarecere la stanga, in sens trigonometric il bag
st[++vf] = a[i];
else
{
while (vf >= 2 && o > 0.0) // daca face intoarcere la dreapta scot pana face intoarcere la stanga.
{
vf--;
o = Intoarcere(st[vf-1], st[vf], a[i]);
}
st[++vf] = a[i];
}
}
}
inline void Write()
{
freopen ("infasuratoare.out", "w", stdout);
printf ("%d\n", vf);
while (vf)
printf ("%lf %lf\n", st[vf].x, st[vf].y), vf--;
}
int main()
{
Read();
Infasoara();
Write();
return 0;
}