Pagini recente » Cod sursa (job #1917285) | Cod sursa (job #2147077) | Cod sursa (job #1310177) | Cod sursa (job #719927) | Cod sursa (job #536780)
Cod sursa(job #536780)
#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
{
double 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 px,int py,int pz)
{
double x1,x2,X,y1,y2,Y,a,b,c,E;
x1=v[px].x;
x2=v[py].x;
y1=v[px].y;
y2=v[py].y;
X=v[pz].x;
Y=v[pz].y;
a=y1-y2;
b=x2-x1;
c=x1*y2-x2*y1;
E=a*X+b*Y+c;
if(Er+E<0) return -1;
if(Er<E) return 1;
return 0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N);
for(i=1;i<=N;i++) scanf("%lf%lf",&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[1]=0;
use[2]=1;
//partea ->
for(i=3;i<=N;i++)
if(!use[i])
{
negativ=f(S[ind-1],S[ind],i);
while(negativ<0&&ind>1)
{
use[S[ind]]=0;
ind--;
negativ=f(S[ind-1],S[ind],i);
}
ind++;
S[ind]=i;
use[i]=1;
}
//partea <-
for(i=N-1;i>0;i--)
if(!use[i])
{
negativ=f(S[ind-1],S[ind],i);
while(negativ<0&&ind>1)
{
use[S[ind]]=0;
ind--;
negativ=f(S[ind-1],S[ind],i);
}
ind++;
S[ind]=i;
use[i]=1;
}
ind--;
printf("%d\n",ind);
for(i=1;i<=ind;i++)
printf("%.6lf %.6lf\n",v[S[i]].x,v[S[i]].y);
return 0;
}