Pagini recente » Cod sursa (job #1214570) | Cod sursa (job #1283307) | Cod sursa (job #1932633) | Cod sursa (job #1168613) | Cod sursa (job #536749)
Cod sursa(job #536749)
#include <stdio.h>
#include <algorithm>
#define DM 120100
#define Er 0.000000000001
using namespace std;
int S[DM],use[DM];
int i,negativ,ind,N;
struct vector
{
float x,y;
}v[DM];
inline bool cmp(const vector &a,const vector &b)
{
if(a.x!=b.x) return a.x<b.x;
else return a.y<b.y;
}
inline int f(int x,int y,int z)
{
float x1,x2,X,y1,y2,Y,a,b,c,E;
x1=v[x].x;
x2=v[y].x;
y1=v[x].y;
y2=v[y].y;
X=v[z].x;
Y=v[z].y;
a=y1-y2;
b=x2-x1;
c=x1*y2-x2*y1;
E=a*X+b*Y+c;
if(E<=Er) return 1;
else return -1;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N);
for(i=1;i<=N;i++) scanf("%f%f",&v[i].x,&v[i].y);
sort(v+1,v+N+1,cmp);
//init
memset(use,0,sizeof(use));
S[1]=1;
S[2]=2;
ind=2;
use[ind]=1;
//partea ->
for(i=3;i<=N;i++)
if(!use[i])
{
negativ=f(S[ind-1],S[ind],i);
while(negativ<0)
{
use[S[ind]]=0;
ind--;
negativ=f(S[ind-1],S[ind],i);
}
ind++;
S[ind]=i;
use[i]=1;
if(use[1]) break;
}
//partea <-
if(!use[1])
for(i=N-1;i>0;i--)
if(!use[i])
{
negativ=f(S[ind-1],S[ind],i);
while(negativ<0)
{
use[S[ind]]=0;
ind--;
negativ=f(S[ind-1],S[ind],i);
}
ind++;
S[ind]=i;
use[i]=1;
if(use[1]) break;
}
ind--;
printf("%d\n",ind);
for(i=ind;i>0;i--)
printf("%.6f %.6f\n",v[S[i]].x,v[S[i]].y);
return 0;
}