Pagini recente » Cod sursa (job #985637) | Cod sursa (job #1739262) | Cod sursa (job #157171) | Cod sursa (job #3257036) | Cod sursa (job #534960)
Cod sursa(job #534960)
#include<stdio.h>
#include<algorithm>
#define E 1e-12
using namespace std;
struct point
{
double x,y;
};
int cmp(double a, double b)
{
if (a + E < b) return -1;
if (b + E < a) return +1;
return 0;
}
bool Pcmp(point a,point b)
{
int r=cmp(a.x,b.x);
if(r==0)return cmp(a.y,b.y)==-1;
return r==-1;
}
int sgn(point a,point b,point c)
{
double A,B,C;
A=a.x-b.x;
B=b.y-a.y;
C=a.x*b.y-a.y*b.x;
return cmp(A*c.x+B*c.y+C,0);
}
long int n,uz[120001],st[120000],k,nr;
point p[120001],pf[120000];
void create()
{
st[0]=0;
st[1]=1;
k=1;
int i=2,pas=1;
sort(p,p+n,Pcmp);
while(uz[0]==0)
{
while(uz[i]>0)
{
if(i==n-1)pas=-1;
i+=pas;
}
while(k>=1&&sgn(p[st[k-1]],p[st[k]],p[i])==-1)uz[st[k--]]=0;
uz[i]=1;
st[++k]=i;
}
nr=k-1;
for(i=0;i<nr;i++)pf[i]=p[st[i]];
pf[k]=p[0];
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%ld\n",&n);
for(int i=0;i<n;i++) scanf("%lf %lf\n",&p[i].x,&p[i].y);
create();
printf("%ld\n",nr);
for(int i=0;i<nr;i++) printf("%lf %lf\n",pf[i].x,pf[i].y);
}