Pagini recente » Cod sursa (job #374756) | Cod sursa (job #719743) | Cod sursa (job #2724829) | Cod sursa (job #1019534) | Cod sursa (job #2402467)
#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, a;
};
POINT P[120005];
double cmp(POINT a, POINT b)
{
return a.a < b.a;
}
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);
}
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;
double tx, ty, miny, minx;
scanf("%d", &n);
miny = INF;
for(i = 1 ; i <= n ; i ++)
{
scanf("%lf%lf", &tx, &ty);
P[i].x = tx;
P[i].y = ty;
if(ty < miny)
{
miny = ty;
minx = tx;
ind = i;
}
else if(ty == miny && tx < minx)
{
minx = tx;
ind = i;
}
}
for(i = 1 ; i <= n ; i ++)
if(i != ind)
P[i].a = atan2(P[i].y - miny, P[i].x - minx);
P[ind].a = -1;
sort(P + 1, P + n + 1, cmp);
P[n + 1] = P[1];
top = 2;
st[1] = 1;
st[2] = 2;
for(i = 3 ; i <= n + 1 ; i ++)
{
while(top >= 2 && ccw(P[st[top - 1]], P[st[top]], P[i]) == -1)
top --;
st[++ top] = i;
}
printf("%d\n", top - 1);
for(i = 1 ; i < top ; i ++)
printf("%f %f\n", P[st[i]].x, P[st[i]].y);
return 0;
}