Pagini recente » Cod sursa (job #2096618) | Cod sursa (job #2916213) | Cod sursa (job #758771) | Cod sursa (job #3178596) | Cod sursa (job #2402634)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 2.e9;
const double PI = 2.0 * acos(0.0);
const double eps = 1.e-12;
struct POINT
{
double x, y;
};
POINT P[120005] , aux;
double cp(POINT P1, POINT P2, POINT P3)
{
return (P2.x - P1.x) * (P3.y - P2.y) - (P2.y - P1.y) * (P3.x - P2.x);
}
double cmp(POINT a, POINT b)
{
return cp(P[1] , a , b) < 0;
}
int ccw(POINT P1, POINT P2, POINT P3)
{
double ccp;
ccp = cp(P1, P2, P3);
if(fabs(ccp) < eps)
return 0;
if(ccp > eps)
return 1;
return -1;
}
int st[120005];
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n, i, ind, top , poz;
double tx, ty;
scanf("%d", &n);
for(i = 1 ; i <= n ; i ++)
{
scanf("%lf%lf", &tx, &ty);
P[i].x = tx;
P[i].y = ty;
}
poz = 1;
for(i = 2 ; i <= n ; i ++)
if(P[i].x < P[poz].x)
poz = i;
aux = P[poz];
P[poz] = P[1];
P[1] = aux;
sort(P + 2, P + n + 1, cmp);
top = 2;
st[1] = 1;
st[2] = 2;
for(i = 3 ; i <= n ; i ++)
{
while(top >= 2 && ccw(P[st[top - 1]], P[st[top]], P[i]) != -1)
top --;
st[++ top] = i;
}
printf("%d\n", top);
for(i = top ; i >= 1 ; i --)
printf("%f %f\n", P[st[i]].x, P[st[i]].y);
return 0;
}