Cod sursa(job #361061)

Utilizator proflaurianPanaete Adrian proflaurian Data 3 noiembrie 2009 17:05:23
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 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;
void read(),solve(),convex_hull(),prints();
int main()
{
    read();
	solve();
	return 0;    
}
void read()
{       
	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];
    }
}