Pagini recente » Cod sursa (job #438762) | Cod sursa (job #1761199) | Cod sursa (job #2476462) | Cod sursa (job #1875616) | Cod sursa (job #327558)
Cod sursa(job #327558)
#include<stdio.h>
#include<algorithm>
#define nmax 120000
#define inf 1000000000
using namespace std;
double cmpf(int,int);
double semn(int,int,int);
int n,pi,ind[nmax],st[nmax];
double x[nmax],y[nmax];
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
x[0]=y[0]=inf;
int p_i=0,i;
for(i=1;i<=n;i++)
{
scanf("%lf %lf",&x[i],&y[i]);
if(x[i]<x[p_i]||(x[i]==x[p_i]&&y[i]<y[p_i]))
p_i=i;
}
pi=p_i;
for(i=1;i<=n;i++)
{
if(i==p_i)
continue;
ind[++ind[0]]=i;
}
sort(ind+1,ind+ind[0]+1,cmpf);
st[0]=1;
st[1]=p_i;
for(i=1;i<=ind[0];i++)
{
while(st[0]>=2&&semn(st[st[0]-1],st[st[0]],ind[i])>0)
st[0]--;
st[++st[0]]=ind[i];
}
st[++st[0]]=p_i;
printf("%d\n",st[0]-1);
reverse(st+1,st+st[0]+1);
for(i=1;i<st[0];i++)
printf("%lf %lf\n",x[st[i]],y[st[i]]);
return 0;
}
double cmpf(int i,int j)
{
return (x[i]-x[pi])*(y[j]-y[pi])<(x[j]-x[pi])*(y[i]-y[pi]);
}
double semn(int i1,int i2,int i3)
{
return x[i1]*y[i2]+x[i2]*y[i3]+x[i3]*y[i1]-y[i1]*x[i2]-y[i2]*x[i3]-y[i3]*x[i1];
}