Pagini recente » Cod sursa (job #545347) | Cod sursa (job #465253) | Cod sursa (job #442200) | Istoria paginii runda/eusebiu_oji_2012_10 | Cod sursa (job #553103)
Cod sursa(job #553103)
#include <stdio.h>
#include <algorithm>
using namespace std;
FILE *f=fopen("infasuratoare.in","r"),*g=fopen("infasuratoare.out","w");
int n,i,st[130000],pi;
double a;
struct punct{double x; double y;};
punct p[130000];
long double semn(punct a,punct b,punct c)
{
return (long double)(a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x);
}
int cmp(punct a,punct b)
{
return ((double)(a.x-p[1].x)*(b.y-p[1].y)<(double)(a.y-p[1].y)*(b.x-p[1].x));
}
int main(void)
{
fscanf(f,"%d",&n);
pi=1;
for (i=1;i<=n;i++)
{
fscanf(f,"%lf%lf",&p[i].x,&p[i].y);
if (p[i].x<p[pi].x || (p[i].x==p[pi].x && p[i].y<p[pi].y)) pi=i;
}
p[0]=p[1];
p[1]=p[pi];
p[pi]=p[0];
sort(p+2,p+n+1,cmp);
st[1]=1;
int k=1;
for (i=2;i<=n;i++)
{
while (k>=2 && semn(p[st[k-1]],p[st[k]],p[i])>0) k--;
k++;
st[k]=i;
}
st[++k]=1;
reverse(st+1,st+k+1);
fprintf(g,"%d\n",k-1);
for (i=1;i<k;i++)
fprintf(g,"%lf %lf\n",p[st[i]].x,p[st[i]].y);
fclose(g);
return 0;
}