Cod sursa(job #571727)

Utilizator tinkyAndrei Ilisei tinky Data 4 aprilie 2011 18:49:27
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<fstream>
#define nmax 120010
#define inf INT_MAX
using namespace std;
struct punct {double x,y,p;};
punct p[nmax],alfa;
int sol[nmax],n;
void citire()
{
	int i;
	ifstream in("infasuratoare.in");
	in>>n;
	for (i=1;i<=n;i++)
		in>>p[i].x>>p[i].y;
}
void cauta_extrema()
{
	int i,poz;
	punct aux;
	alfa.x=alfa.y=poz;
	for (i=1;i<=n;i++)
	{
		if (p[i].x<alfa.x)
		{
			alfa=p[i];
			poz=i;
		}
		else if (p[i].x==alfa.x&&p[i].y<alfa.y)
		{	
			alfa=p[i];
			poz=i;
		}
	}
	aux=p[poz];
	p[poz]=p[1];
	p[1]=aux;	
}
	
	
long long sens(punct a,punct b,punct c)
{
	long long x;
	//x=a.x*b.y+c.x*a.y+b.x*c.y-c.x*b.y-a.x*c.y-b.xa.y;
	x=a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
	if (x>0)
		return 1;
	if (x<0)
		return -1;
	return 0;
}
void panta(punct &a)
{	a.p=(-alfa.y+a.y)/(-alfa.x+a.x);	}

int cmp(punct a,punct b)
{	
	if (a.p==b.p)
		return a.x<b.x;
	return a.p<b.p;
}

int main()
{
	int i,k=0;
	citire();
	cauta_extrema();
	for (i=1;i<=n;i++)
		panta(p[i]);
	sort(p+2,p+n+1,cmp);
	ofstream out("infasuratoare.out");
	//out<<alfa.x<<" "<<alfa.y<<'\n';
	//for (i=1;i<=n;i++)
	//	out<<p[i].x<<" "<<p[i].y<<" "<<p[i].p<<'\n';
	sol[++k]=1;
	for (i=2;i<=n;i++)
	{
		if (sens(p[i-1],p[i],p[i+1])==1)
			sol[++k]=i;
	}
	out<<k<<'\n';
	for (;k>0;k--)
		out<<p[sol[k]].x<<" "<<p[sol[k]].y<<'\n';
	
}