Cod sursa(job #239126)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 4 ianuarie 2009 10:57:46
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include<stdio.h>
#define N 120010
int n,i,stack[N],top;
long double a[N],b[N],epsilon=0.00000001;
void readd(),sortare(),convex_hull(),sw(int i1,int i2),
hd(int ic,int nc),prints();
int ord(int i0,int i1,int i2);
long double det(int i1,int i2,int i3),dist(int i1,int i2);
int main()
{
	readd();
	sortare();
	convex_hull();
	prints();
	return 0;
}
void readd()
{       long double aa,bb;
	int imin;
	freopen("infasuratoare.in","rt",stdin);
	freopen("infasuratoare.out","wt",stdout);
	scanf("%d",&n);
	scanf("%Lf%Lf",&a[0],&b[0]);
	aa=a[0];bb=b[0];imin=0;
	for(i=1;i<n;i++)
	{ scanf("%Lf%Lf",&a[i],&b[i]);
	  if(a[i]<aa||(a[i]==aa&&b[i]<bb))
	  { imin=i;aa=a[i];bb=b[i];}
	}
	sw(imin,0);
}
void sortare()
{
	int nn=n-1;
	for(i=nn/2;i>=1;i--)hd(i,nn);
	for(i=nn;i>=1;i--){sw(1,i);hd(1,i-1);}
}
void hd(int ic,int nc)
{
	int is=ic<<1;
	if(is>nc)return;
	if(is<nc)if(ord(0,is,is+1))is++;
	if(ord(0,ic,is)){sw(is,ic);hd(is,nc);}
}
int ord(int i0,int i1,int i2)
{
	long double delta=det(i0,i1,i2),d1,d2;
	if(delta>epsilon)return 1;
	if(delta<-epsilon)return 0;
	d1=dist(0,i1);d2=dist(0,i2);
	if(d2-d1>epsilon)return 1;
	return 0;
}
long double det(int i1,int i2,int i3)
{
	long double ret;
	ret=a[i1]*b[i2]+a[i2]*b[i3]+a[i3]*b[i1]-
	b[i1]*a[i2]-b[i2]*a[i3]-b[i3]*a[i1];
	return ret;
}
void sw(int i1,int i2)
{
	long double aux;
	aux=a[i1];a[i1]=a[i2];a[i2]=aux;
	aux=b[i1];b[i1]=b[i2];b[i2]=aux;
}
void convex_hull()
{
	stack[0]=0;
	stack[1]=1;
	top=1;
	for(i=2;i<n;i++)
	{ while(!ord(stack[top-1],stack[top],i))top--;
	  top++;stack[top]=i;
	}
}
void prints()
{
	printf("%d\n",top+1);
	for(i=0;i<=top;i++)
	printf("%.6Lf %.6Lf\n",a[stack[i]],b[stack[i]]);
}
long double dist(int i1,int i2)
{
	return (a[i1]-a[i2])*(a[i1]-a[i2])+(b[i1]-b[i2])*(b[i1]-b[i2]);
}