Cod sursa(job #719406)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 21 martie 2012 19:44:00
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<fstream>
#include<algorithm>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int i,n,d,st[120024];

struct point
{
	long double x,y;
}p[120024];
	
long double isleft(point a,point b,point c)
{
	return ((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y));
}

bool comp(point a,point b)
{
	long double k=isleft(p[1],a,b);
	if(k>0) return 1;
	return 0;
}

int main()
{
	f>>n;
	f>>p[1].x>>p[1].y;
	
	for(i=2;i<=n;++i)
	{
		f>>p[i].x>>p[i].y;
		
		if((p[i].x<p[1].x)||(p[i].x==p[1].x&&p[i].y<p[1].y))
		{
			point aux=p[1];
			p[1]=p[i];
			p[i]=aux;
		}
	}
	
	sort(p+2,p+n+1,comp);
	
	st[++d]=1;
	
	for(i=2;i<=n;++i) 
	{
		while(d>1&& isleft(p[st[d-1]],p[st[d]],p[i])<0) --d;
		st[++d]=i;
	}
	
	g<<d<<"\n";
	
	for(i=1;i<=d;++i) g<<p[st[i]].x<<" "<<p[st[i]].y<<"\n";
	
	f.close();
	g.close();
	
	return 0;
}