Pagini recente » Cod sursa (job #2552354) | Cod sursa (job #58096) | Cod sursa (job #2636460) | Cod sursa (job #767087) | Cod sursa (job #420477)
Cod sursa(job #420477)
//O(N^2*H)
#include<iostream>
#include<string>
using namespace std;
#define inf 2000000000
#define DL long double
#define NM 120005
double X[NM],Y[NM];
int conv[NM];
char isin[NM];
int N;
double ab(double val)
{
if(val>=0) return val;
return -val;
}
double ec(int p1,int p2,int p0)
{
return (double)((DL)(X[p2]-X[p1])*(DL)(Y[p0]-Y[p1])-(DL)(X[p0]-X[p1])*(DL)(Y[p2]-Y[p1]));
}
int all_on_one_side(int p1,int p2)
{
int sign,i;
for(i=1;i<=N;++i)
if(i!=p1 && i!=p2)
{
int val=(int)ec(p1,p2,i);
sign=val/ab(val);
break;
}
for(;i<=N;++i)
if(i!=p1 && i!=p2)
{
int val=(int)ec(p1,p2,i);
int nsign=val/ab(val);
if(nsign!=sign) return 0;
}
return 1;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N);
for(int i=1;i<=N;++i)
scanf("%lf %lf",&X[i],&Y[i]);
X[0]=inf;
conv[1]=0;
for(int i=1;i<=N;++i)
{
double lx=X[conv[1]];
double ly=Y[conv[1]];
if(X[i]<lx || (X[i]==lx && Y[i]<ly)) conv[1]=i;
}
int H=1;
isin[conv[1]]=1;
while(1)
{
int found=0;
for(int i=1;i<=N;++i)
if(!isin[i] && all_on_one_side(conv[H],i))
{
conv[++H]=i;
isin[i]=1;
found=1;
break;
}
if(!found) break;
}
printf("%d\n",H);
for(int i=1;i<=H;++i)
printf("%lf %lf\n",X[conv[i]],Y[conv[i]]);
return 0;
}