Pagini recente » Cod sursa (job #1116107) | Cod sursa (job #914270) | Cod sursa (job #280790) | Cod sursa (job #2505461) | Cod sursa (job #411600)
Cod sursa(job #411600)
#include<stdio.h>
#include<algo.h>
using namespace std;
FILE *f,*g;
long n,i,a[120100],k,st[120100],ok,ct,cauta; float x[120100],y[120100],negasit,viz[120100];
int cmp(int a,int b)
{ return x[a]<x[b]||x[a]==x[b]&&y[a]<y[b]; }
float det(long v1,long v2,long v3)
{ return x[a[v1]]*y[a[v2]]+x[a[v2]]*y[a[v3]]-x[a[v3]]*y[a[v2]]-x[a[v2]]*y[a[v1]]-y[a[v3]]*x[a[v1]]+y[a[v1]]*x[a[v3]]; }
int main()
{ f=fopen("infasuratoare.in","r"); g=fopen("infasuratoare.out","w");
fscanf(f,"%ld",&n); for(i=1;i<=n;i++) fscanf(f,"%f%f",&x[i],&y[i]);
for(i=1;i<=n;i++) a[i]=i;
sort(a+1,a+n+1,cmp);
k=2; st[1]=1; st[2]=2; ok=1; ct=3;
while(ok)
{ cauta=1; ct=st[k]+1;
while(cauta)
if(det(ct,st[k],st[k-1])>=0) { k++; st[k]=ct; cauta=0; }
else k--;
if(st[k]==n) ok=0;
}
for(i=1;i<=k;i++) viz[st[i]]=1; ok=1; viz[st[1]]=0;
while(ok)
{ cauta=1; negasit=1; for(i=n;i>=1&&negasit;i--) if(viz[i]==0) { negasit=0; ct=i; }
while(cauta)
if(det(ct,st[k],st[k-1])>=0) { k++; st[k]=ct; viz[st[k]]=1; cauta=0; }
else k--;
if(st[k]==st[1]) ok=0;
}
fprintf(g,"%ld\n",k-1);
for(i=1;i<k;i++) fprintf(g,"%f %f\n",x[a[st[i]]],y[a[st[i]]]);
fclose(g);
return 0;
}