# Cod sursa(job #2001924)

Utilizator Data 18 iulie 2017 01:40:04 Infasuratoare convexa 100 cpp done Arhiva educationala 1.46 kb
``````#include<stdio.h>
#include<utility>
#include<algorithm>
#define N 120010
#define POINT pair< double , double >
#define X first
#define Y second
#define DET(A,B,C) A.X*B.Y+B.X*C.Y+C.X*A.Y-A.Y*B.X-B.Y*C.X-C.Y*A.X
#define DIST(A,B) (A.X-B.X)*(A.X-B.X)+(A.Y-B.Y)*(A.Y-B.Y)
using namespace std;
int n,i,vf,comp(POINT A,POINT B),TRIG(POINT A,POINT B,POINT C);
POINT P[N],ST[N];
double u,v,mic=0.00000001;
int main()
{
solve();
return 0;
}
{
POINT Q;int iq;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
scanf("%lf%lf",&u,&v);P[0]=make_pair(u,v);
Q=P[0];iq=0;
for(i=1;i<n;i++)
{
scanf("%lf%lf",&u,&v);P[i]=make_pair(u,v);
if(P[i]<Q){iq=i;Q=P[i];}
}
Q=P[iq];P[iq]=P[0];P[0]=Q;
}
void solve()
{
sort(P+1,P+n,comp);
convex_hull();
printf("%d\n",vf+1);
for(i=0;i<=vf;i++)
printf("%.6lf %.6lf\n",ST[i].X,ST[i].Y);
}
int TRIG(POINT A,POINT B,POINT C)
{
double delta=DET(A,B,C),AB,AC;
if(delta>mic)return 1;
if(delta<-mic)return 0;
AB=DIST(A,B);AC=DIST(A,C);
if(AC-AB>mic)return 1;
return 0;
}
int comp(POINT A,POINT B)
{
return TRIG(P[0],A,B);
}
void convex_hull()
{
ST[0]=P[0];ST[1]=P[1];vf=1;
for(i=2;i<n;i++)
{
while(!TRIG(ST[vf-1],ST[vf],P[i]))vf--;
vf++;ST[vf]=P[i];
}
}
``````