Pagini recente » Cod sursa (job #198065) | Cod sursa (job #2211581)
#include <stdio.h>
#include <algorithm>
using namespace std;
FILE *f,*g;
struct point
{
double x,y;
}v[120002];
bool been[120002];
int st[120002];
int n,h;
bool cmp (point a, point b)
{
if(a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
}
void read()
{
fscanf(f,"%d",&n);
for(int i=1; i<=n; i++)
fscanf(f,"%lf %lf",&v[i].x,&v[i].y);
sort(v+1,v+n+1,cmp);
}
double determinant(point a, point b, point c)
{
return ((a.x*b.y+b.x*c.y+c.x*a.y)-(b.y*c.x+c.y*a.x+a.y*b.x));
}
void infasuratoare()
{ int k,i,q;
st[1]=1,st[2]=2;
been[2]=1;
k=2;
i=3;
q=1;
while(!been[1])
{
while(been[i])
{
if(i==n)
q=-1;
i+=q;
}
while(k>=2 && determinant(v[st[k-1]],v[st[k]],v[i])<0)
been[st[k--]]=0;
st[++k]=i;
been[i]=1;
}
h=k-1;
}
int main()
{ int p;
f=fopen("infasuratoare.in","r");
g=fopen("infasuratoare.out","w");
read();
infasuratoare();
fprintf(g,"%d\n",h);
for(int i=1; i<=h; i++)
fprintf(g,"%6f %6f\n",v[st[i]].x,v[st[i]].y);
fclose(f);
fclose(g);
return 0;
}