Cod sursa(job #720200)

Utilizator valiro21Valentin Rosca valiro21 Data 22 martie 2012 14:02:30
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include <cstdio>
#include <algorithm>
#define NMax 120021
#include <list>
#include <cmath>
#define INFINIT 1000000001

using namespace std;

struct cord{
	double x,y;
};

list<double> lix,liy;
cord ve[NMax];
long start,n,mini;
double minx,miny,dx1,dx2,dy1,dy2,x,y;

bool compare(cord p1,cord p2)
{
	double sin1=(double)(p1.x-minx)/sqrt((p1.x-minx)*(p1.x-minx)+(p1.y-miny)*(p1.y-miny)),sin2=(double)(p2.x-minx)/sqrt((p2.x-minx)*(p2.x-minx)+(p2.y-miny)*(p2.y-miny));
	
	if(p1.x<minx)
		sin1=-sin1;
	
	if(p2.x<minx)
		sin2=-sin2;
	
	if( ((sin1<0 && sin2>0) || (sin1>0 && sin2<0)) &&sin2<sin1)
			return 1;
	
	if(sin2>sin1)
		return 1;
	
	
	
	return 0;
}

bool right_turn(double dx1,double dy1,double dx2,double dy2,double px,double py)
{
	double a=(double)(dy2-dy1)/(dx2-dx1),b=(double)dy1-a*dx1;
	long pya=(long)(a*px+b);
	if(py>=pya)
		return 0;
	return 1;
}

void bck()
{
	list<double>::iterator end1x=lix.end(),end2x=end1x,end1y=liy.end(),end2y=end1y;
	end1x--;end2x--;end2x--;
	end1y--;end2y--;end2y--;
	
	for(;start<=n;start++)
 		if(!right_turn(*end2x,*end2y,*end1x,*end1y,ve[start].x,ve[start].y))
		{
			lix.push_back(ve[start].x);
			liy.push_back(ve[start].y);
			bck();
		}
		else
		{
			lix.pop_back();
			liy.pop_back();
			bck();
		}
}

int main()
{
	freopen("infasuratoare.in","rt",stdin);
	freopen("infasuratoare.out","wt",stdout);
	
	scanf("%ld",&n);
	minx=miny=INFINIT;
	for(long i=1;i<=n;i++)
	{
		scanf("%lf %lf",&x,&y);
		ve[i].x=x;ve[i].y=y;
		if(y<miny)
			minx=x,miny=y,mini=i;
		else
			if(miny==y && x<minx)
				minx=x,mini=i;
	}
	
	sort(ve+1,ve+n+1,compare);
	
	lix.push_back(minx);
	liy.push_back(miny);
	lix.push_back(ve[2].x);
	liy.push_back(ve[2].y);
	dx1=minx;dy1=miny;
	dx2=ve[2].x;dy2=ve[2].y;
	
	start=3;
	bck();
	
	printf("%ld\n",lix.size());
	while(!lix.empty())
	{
		printf("%lf %lf\n",lix.front(),liy.front());
		lix.pop_front();liy.pop_front();
	}
	
	return 0;
}