Pagini recente » Cod sursa (job #1593368) | Cod sursa (job #383224) | Cod sursa (job #2821891) | Cod sursa (job #2437414) | Cod sursa (job #1907536)
#include <cstdio>
#include <cmath>
#include <algorithm>
struct pct {double x,y;} P[120010];
int n,vfsup=-1,vfinf=-1;
pct stsup[120010],stinf[120010];
bool comppct(pct x,pct y)
{
return x.x<y.x||x.x==y.x&&x.y<y.y;
}
int parte(pct a,pct b,pct c)
{
double det=a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-a.x*c.y-a.y*b.x;
if(det<0)return -1;
return 1;
}
int main()
{
FILE *f=fopen("infasuratoare.in","r");
fscanf(f,"%d",&n);
int i;
for(i=1;i<=n;i++)
fscanf(f,"%lf%lf",&P[i].x,&P[i].y);
std::sort(P+1,P+n+1,comppct);
stsup[++vfsup]=P[1];
stinf[++vfinf]=P[1];
for(i=2;i<=n-1;i++)
if(parte(P[1],P[i],P[n])==-1)
{//partea superioara
if(vfsup==0)stsup[++vfsup]=P[i];
else
{//tre sa vad cum stau cu stsup[vfsup-1], stsup[vfsup] shi P[i]
while(vfsup>0 && parte(stsup[vfsup-1],stsup[vfsup],P[i])==1)vfsup--;
stsup[++vfsup]=P[i];
}
}
else
{//partea inferioara
if(vfinf==0)stinf[++vfinf]=P[i];
else
{//tre sa vad cum stau cu stinf[vfinf-1], stinf[vfinf] shi P[i]
while(vfinf>0 && parte(stinf[vfinf-1],stinf[vfinf],P[i])==-1)vfinf--;
stinf[++vfinf]=P[i];
}
}
//repet pentru ambele stive cu ultimul punct (fara a mai verifica partea)
if(vfsup==0)stsup[++vfsup]=P[n];
else
{//tre sa vad cum stau cu stsup[vfsup-1], stsup[vfsup] shi P[n]
while(vfsup>0 && parte(stsup[vfsup-1],stsup[vfsup],P[n])==1)vfsup--;
stsup[++vfsup]=P[n];
}
if(vfinf==0)stinf[++vfinf]=P[n];
else
{//tre sa vad cum stau cu stinf[vfinf-1], stinf[vfinf] shi P[n]
while(vfinf>0 && parte(stinf[vfinf-1],stinf[vfinf],P[n])==-1)vfinf--;
stinf[++vfinf]=P[n];
}
FILE *g=fopen("infasuratoare.out","w");
fprintf(g,"%d\n",vfsup+vfinf);
for(i=vfsup;i>=0;i--)
fprintf(g,"%13.12lf %13.12lf\n",stsup[i].x,stsup[i].y);
for(i=1;i<vfinf;i++)
fprintf(g,"%13.12lf %13.12lf\n",stinf[i].x,stinf[i].y);
return 0;
}