Mai intai trebuie sa te autentifici.
Cod sursa(job #1398248)
Utilizator | Data | 24 martie 2015 08:19:50 | |
---|---|---|---|
Problema | Infasuratoare convexa | Scor | 20 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 2.34 kb |
#include<cstdio>
#include<algorithm>
FILE *fin,*fout;
struct str
{
double x;
double y;
double numi;
double numa;
} vect[120100];
int comp(str a,str b)
{
return a.numi*b.numa<a.numa*b.numi;
}
int check(int xa,int ya,int xb,int yb,int xc,int yc)
{
double x=xa*yb+xb*yc+xc*ya-xc*yb-xa*yc-xb*ya;
//fprintf(fout,"%lf\n",x);
if(x>0)
{
return 1;
}
return 0;
}
int q[120100];
int main()
{
fin=fopen("infasuratoare.in","r");
fout=fopen("infasuratoare.out","w");
int n,p,ox=1000000000,oy=1000000000;
fscanf(fin,"%d",&n);
for(int i=1;i<=n;i++)
{
fscanf(fin,"%lf %lf",&vect[i].x,&vect[i].y);
//fprintf(fout,"%lf %lf\n",vect[i].x,vect[i].y);
if(ox>vect[i].x)
{
ox=vect[i].x;
oy=vect[i].y;
p=i;
}
else if(ox==vect[i].x)
{
if(oy>vect[i].y)
{
oy=vect[i].y;
p=i;
}
}
}
std::swap(vect[1].x,vect[p].x);
std::swap(vect[1].y,vect[p].y);
for(int i=2;i<=n;i++)
{
vect[i].numi=vect[i].y-vect[1].y;
vect[i].numa=vect[i].x-vect[1].x;
}
std::sort(vect+2,vect+n+1,comp);
/*for(int i=1;i<=n;i++)
{
fprintf(fout,"%lf %lf\n",vect[i].x,vect[i].y);
}*/
q[0]=3;
q[1]=1;
q[2]=2;
for(int i=3;i<=n;i++)
{
if(check(vect[q[q[0]-2]].x,vect[q[q[0]-2]].y,vect[q[q[0]-1]].x,vect[q[q[0]-1]].y,vect[i].x,vect[i].y)==1)
{
q[q[0]]=i;
q[0]++;
}
else
{
//fprintf(fout,"%lf %lf %lf %lf %lf %lf\n",vect[q[q[0]-2]].x,vect[q[q[0]-2]].y,vect[q[q[0]-1]].x,vect[q[q[0]-1]].y,vect[i].x,vect[i].y);
while(check(vect[q[q[0]-2]].x,vect[q[q[0]-2]].y,vect[q[q[0]-1]].x,vect[q[q[0]-1]].y,vect[i].x,vect[i].y)==0)
{
q[0]--;
}
q[q[0]]=i;
q[0]++;
//fprintf(fout,"%lf %lf %lf %lf %lf %lf\n",vect[q[q[0]-2]].x,vect[q[q[0]-2]].y,vect[q[q[0]-1]].x,vect[q[q[0]-1]].y,vect[i].x,vect[i].y);
}
}
fprintf(fout,"%d\n",q[0]-1);
for(int i=1;i<q[0];i++)
{
fprintf(fout,"%lf %lf\n",vect[q[i]].x,vect[q[i]].y);
}
}