Cod sursa(job #700627)

Utilizator Oancea.CatalinOancea Catalin Oancea.Catalin Data 1 martie 2012 11:14:34
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include<fstream>
#include<iomanip>
#include<algorithm>
using namespace std;
#define IN "infasuratoare.in"
#define OUT "infasuratoare.out"
#define MaxN 120001
#define INF 100000
fstream f(IN, ios::in), g(OUT, ios::out);
int n, i, poz, A[MaxN], nr;
double pxmin, pymin;
struct PUNCT{
	double x;
	double y;
	double panta;
}point[MaxN];
double PANTA(int X)
{
	if(point[0].x == point[X].x) return INF;
	else return (point[X].y-point[0].y)/(point[X].x-point[0].x);
}
bool cmp(PUNCT X, PUNCT Y)
{
	return (X.panta<Y.panta);
}
double DETERMINANT(int x1,int y1,int z1)
{
	double s1=0;
	s1+=(point[x1].x*point[y1].y);
	s1+=(point[y1].x*point[z1].y);
	s1+=(point[x1].y*point[z1].x);
	s1-=(point[y1].y*point[z1].x);
	s1-=(point[x1].x*point[z1].y);
	s1-=(point[y1].x*point[x1].y);
	return s1;
}
int main()
{
	f>>n;
	f>>point[1].x>>point[1].y;
	pxmin=point[1].x; pymin=point[1].y; poz=1;
	for(i=2; i<=n; i++){
		f>>point[i].x>>point[i].y;
		if(point[i].x<pxmin){
			pxmin=point[i].x; pymin=point[i].y; poz=i;
		}
		else if(point[i].x==pxmin && point[i].y<pymin){
			pxmin=point[i].x; pymin=point[i].y; poz=i;
		}
	}
	point[0]=point[poz];
	point[poz]=point[n];
	n--;
	
	for(i=1; i<=n; i++)
		point[i].panta=PANTA(i);
	
	sort(point+1, point+n+1, cmp);
//	for(i=1; i<=n; i++)
//		g<<point[i].x<<" "<<point[i].y<<" "<<point[i].panta<<"\n";
	
	A[0]=0; A[1]=1; nr=1;
	for(i=2; i<=n; i++)
	{
		while(nr>0 && DETERMINANT(A[nr-1],A[nr],i)<0)
			nr--;
		A[++nr]=i;
	}
	g<<nr+1<<"\n";
	for(i=0; i<=nr; i++)
		g<<fixed<<setprecision(12)<<point[A[i]].x<<" "<<point[A[i]].y<<"\n";
}