Pagini recente » Cod sursa (job #2083571) | Cod sursa (job #2029497) | Cod sursa (job #2937976) | Cod sursa (job #2980495) | Cod sursa (job #1966082)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
struct punct {double x, y;}P[120001],st[120001],minim,aux;
int vf,n,i,poz;
double minx,miny,o;
bool cmp(punct A, punct B)
{
if(atan(A.y/A.x)==atan(B.y/B.x))
return sqrt((A.x-minim.x)*(A.x-minim.x) -(A.y-minim.y)*(A.y-minim.y))<sqrt((B.x-minim.x)*(B.x-minim.x)-(B.y-minim.y)*(B.y-minim.y));
else
return atan(A.y/A.x)<atan(B.y/B.x);
}
void pop()
{
vf--;
}
void push(punct A)
{
vf++;
st[vf]=A;
}
double prod(punct A, punct B, punct C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
minim.x=10000000;
minim.y=10000000;
for(i=1; i<=n; i++)
{scanf("%lf%lf", &P[i].x, &P[i].y);
if(P[i].x<minim.x)
{minim=P[i];
poz=i;}
else
if(P[i].x==minim.x)
if(P[i].y<minim.y)
{minim=P[i];
poz=i;}
}
aux=P[1];
P[1]=P[poz];
P[poz]=aux;
sort(P+1,P+n+1,cmp);
vf=0;
push(P[1]);
push(P[2]);
for(i=3; i<=n; i++)
{
o=prod(st[vf-1],st[vf],P[i]);
if(o==0)
{
pop();
push(P[i]);
}
else
if(o>0)
{
push(P[i]);
}
else
{
while(vf>1 && o<=0)
{
pop();
o=prod(st[vf-1],st[vf],P[i]);
}
push(P[i]);
}
}
printf("%d\n", vf+1);
for(i=1; i<=vf; i++)
printf("%lf %lf\n", st[i].x, st[i].y);
printf("%lf %lf\n", minim.x, minim.y);
return 0;
}