Pagini recente » Cod sursa (job #2129858) | Cod sursa (job #638935) | Cod sursa (job #2193694) | Cod sursa (job #1067887) | Cod sursa (job #411627)
Cod sursa(job #411627)
#include<stdio.h>
#include<algo.h>
using namespace std;
FILE *f,*g;
long n,i,a[120100],k,st[120100],ok,ct,cauta,nr,simb; double 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,"%lf%lf",&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==1) { k++; st[k]=ct; cauta=0; }
else if(k>1) k--;
if(st[k]==n) ok=0;
}
for(i=n;i>=1&&negasit;i--) if(viz[i]==0) { negasit=0; ct=i; } simb=i; simb++;
for(i=1;i<=k;i++) viz[st[i]]=1; ok=1; viz[st[1]]=0; nr=k;
while(ok)
{ cauta=1; negasit=1; for(i=simb;i>=1&&negasit;i--) if(viz[i]==0) { negasit=0; ct=i; simb=i; }
while(cauta)
if(det(ct,st[k],st[k-1])>=0||k==nr) { k++; st[k]=ct; viz[st[k]]=1; cauta=0; }
else if(k>nr) k--;
if(st[k]==st[1]) ok=0;
}
fprintf(g,"%ld\n",k-1); fprintf(g,"%lf %lf\n",x[a[st[1]]],y[a[st[1]]]);
for(i=k-1;i>=2;i--) fprintf(g,"%lf %lf\n",x[a[st[i]]],y[a[st[i]]]);
fclose(g);
return 0;
}