Pagini recente » Cod sursa (job #798836) | Cod sursa (job #2307855) | Cod sursa (job #1563008) | Cod sursa (job #1897262) | Cod sursa (job #1280367)
//#include <iostream>
#include <cstdio>
#include <algorithm>
#define nmax 120001
#define inf 100000000000
using namespace std;
FILE *f=fopen("infasuratoare.in","r"),*g=fopen("infasuratoare.out","w");
struct punct
{
float x,y;
}v[nmax],p;
int st[nmax],viz[nmax];
float det(punct a, punct b, punct c)
{
return a.x*(b.y-c.y)-a.y*(b.x-c.x)+b.x*c.y-c.x*b.y;
}
bool comp(punct a, punct b)
{
return det(a,p,b)>0;
}
int main()
{
int i,j,n,k,semn=1,poz;
p.x = inf;
p.y = inf;
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
{fscanf(f,"%f %f",&v[i].x,&v[i].y);
if(v[i].x<p.x)
{
p=v[i];
poz=i;
}
if(v[i].x==p.x && v[i].y<p.y)
{
p=v[i];
poz=i;
}
}
swap(v[poz], v[1]);
sort(v+2,v+1+n,comp);
st[1]=1;
k=1; viz[2]=1;
for(i=2;i<=n;i++)
{
while(k>1&&det(v[st[k-1]],v[st[k]],v[i])>=0)
k--;
st[++k]=i;
}
fprintf(g,"%d\n",k-1);
for(i=1;i<k;i++)
fprintf(g,"%.6f %.6f\n",v[st[i]].x,v[st[i]].y);
return 0;
}