Pagini recente » Cod sursa (job #2788075) | Cod sursa (job #388423) | Cod sursa (job #311352) | Cod sursa (job #2921917) | Cod sursa (job #685873)
Cod sursa(job #685873)
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE*f=fopen("infasuratoare.in","r");
FILE*g=fopen("infasuratoare.out","w");
int n,poz,nr,stv[120001];
double miny,minx;
struct pct
{
double x,y,ctg;
}v[120001];
int cmp(pct a,pct b)
{
return a.ctg>b.ctg;
}
int ver(double x1,double x2,double x3,double y1,double y2,double y3)
{
double x=(x3-x2)*(y1-y2)-(x1-x2)*(y3-y2);
if(x<0)
return 1;
return 0;
}
int main()
{
fscanf(f,"%d",&n);
miny=1000000000;
for(int i=1;i<=n;++i)
{
fscanf(f,"%lf %lf",&v[i].x,&v[i].y);
if(miny>v[i].y)
{
miny=v[i].y;
minx=v[i].x;
poz=i;
}
}
v[poz]=v[1];
v[1].x=v[1].y=v[1].ctg=0;
for(int i=2;i<=n;++i)
{
v[i].x-=minx;
v[i].y-=miny;
v[i].ctg=v[i].x/v[i].y;
}
sort(v+2,v+n+1,cmp);
stv[1]=1;
stv[2]=2;
nr=2;
for(int i=3;i<=n;++i)
{
while(nr>2&&ver(v[stv[nr-1]].x,v[stv[nr]].x,v[i].x,v[stv[nr-1]].y,v[stv[nr]].y,v[i].y))
--nr;
stv[++nr]=i;
}
fprintf(g,"%d\n",nr);
for(int i=1;i<=nr;++i)
fprintf(g,"%lf %lf\n",v[stv[i]].x+minx,v[stv[i]].y+miny);
fclose(g);
fclose(f);
return 0;
}