Pagini recente » Cod sursa (job #2607744) | Cod sursa (job #2161098) | Cod sursa (job #1821095) | Cod sursa (job #2667051) | Cod sursa (job #2065335)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps=1.e-14;
struct POINT
{
double x,y;
}ll;
int ccw(const POINT &A, const POINT &B, const POINT &C)
{
double cp = (B.x -A.x) * (C.y - B.y) - (B.y - A.y) * (C.x - B.x);
if(fabs(cp)<eps)
return 0;
if(cp>=eps)
return 1;
return -1;
}
double dist(const POINT &A, const POINT &B)
{
return sqrt ((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
class MyComp
{
public:
bool operator () (const POINT &A, const POINT &B)
{
int cp;
double d1, d2;
cp = ccw(ll, A, B);
if(cp==0)
{
d1=dist(ll,A);
d2=dist(ll,B);
if(d1 - d2 <= -eps)
return 1;
else
return 0;
}
if(cp==-1)
return 0;
return 1;
}
};
const int N=120000;
POINT P [N+10];
int H [N+10];
int n;
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int i, poz, u, cp;
POINT aux;
scanf("%d", &n);
ll.x = ll.y = 1000000000;
for(i=0 ; i<n ; i++)
{
scanf("%lf%lf", &P[i].x, &P[i].y);
if(P[i].y-ll.y <= -eps || (fabs(P[i].y-ll.y) < eps && P[i].x - ll.x <= -eps) )
{
ll = P[i];
poz = i;
}
}
aux=P[0];
P[0]=P[poz];
P[poz]=aux;
sort(P+1 , P+n , MyComp ());
P[n] = P[0];
H[1] = 0;
H[2] = 1;
i=2;
u=2;
while(i<=n)
{
cp=ccw(P[H[u-1]] , P[H[u]] , P[i]);
if(cp>0)
{
H[++u] = i;
++i;
}
else u--;
}
u--;
printf("%d\n", u);
for(i=1 ; i<=u ; i++)
printf("%.6f %.6f\n", P[H[i]].x, P[H[i]].y);
return 0;
}