Pagini recente » Cod sursa (job #2849247) | Cod sursa (job #2827869) | Cod sursa (job #896570) | Cod sursa (job #2571133) | Cod sursa (job #553654)
Cod sursa(job #553654)
#include<fstream.h>
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct{ double x,y;} p[120001];
int s[120001],r,k,infinit,v[120001],vf,n;
char nr[31];
void citire()
{ f>>n;
for(int i=1;i<=n;i++) f>>p[i].x>>p[i].y;
f.close();
}
void reper()
{ r=1;
for(int i=2;i<=n;i++)
if(p[i].x<p[r].x||p[i].x==p[r].x&&p[i].y<p[r].y) r=i;
}
int mai_mic(int i,int j)
{ double a=(p[i].x-p[r].x)*(p[j].x-p[r].x);
double b=(p[i].y-p[r].y)*(p[j].x-p[r].x)-(p[i].x-p[r].x)*(p[j].y-p[r].y);
if(a<0&&b>0||a>0&&b<0) return 1;
return 0;
}
void ordonare()
{ k=0;
int i;
for(i=1;i<=n;i++)
if(i!=r)
if(p[i].x==p[r].x)
if(!infinit||p[infinit].y<p[i].y) infinit=i;
else;
else { k++;
v[k]=i;
}
int ord,m=k,aux;
do{ ord=1;
for(i=1;i<m;i++)
if(mai_mic(v[i+1],v[i]))
{ ord=0;
aux=v[i];
v[i]=v[i+1];
v[i+1]=aux;
}
m--;
} while(!ord);
}
int elim(int i)
{ double a=p[v[i]].x-p[s[vf]].x;
double b=(p[s[vf-1]].y-p[v[i]].y)*a-(p[v[i]].y-p[s[vf]].y)*(p[s[vf-1]].x-p[v[i]].x);
//g<<"elim "<<a<<' '<<b<<'\n';
if(b<0&&a>0) return 1;
return 0;
}
void stiva()
{ s[1]=r;
s[2]=v[1];
vf=2;
for(int i=2;i<=k;i++)
{ while(elim(i)&&vf>2) vf--;
vf++;
s[vf]=v[i];
//for(int j=vf;j>0;j--) g<<s[j]<<' ';
//g<<'\n';
}
}
void afis()
{ if(infinit) g<<vf+1<<'\n';
else g<<vf<<'\n';
for(int i=1;i<=vf;i++)
g<<p[s[i]].x<<' '<<p[s[i]].y<<'\n';
/*{ double aux=p[s[i]].x;
int z=10;
while(p[s[i]].x/z) z*=10;
z/=10;
nr[0]=p[s[i]].x/z;*/
if(infinit) g<<p[infinit].x<<' '<<p[infinit].y<<'\n';
//g.close();
}
int main()
{ citire(); reper(); ordonare(); stiva(); afis();
//for(int i=1;i<=k;i++) g<<v[i]<<' ';
g.close();
return 0;
}