Cod sursa(job #943009)

Utilizator tibi9876Marin Tiberiu tibi9876 Data 23 aprilie 2013 23:38:23
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<fstream>
#include<algorithm>
using namespace std;

struct pct
{
	double x,y;
};

pct a[120001],s[120001];
int i,n,k,x;
double mx,my;

double ar(pct a,pct b,pct c)
{
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

bool cmp(pct x,pct y)
{
	return ar(a[1],x,y)>0;
}

int main()
{
	ifstream f("infasuratoare.in");
	ofstream g("infasuratoare.out");
	f >> n;
	my=1 << 30;
	for (i=1;i<=n;i++)
	{
		f >> a[i].x >> a[i].y;
		if ((a[i].y<my) || ((a[i].y==my) && (a[i].x<mx)))
		{
			x=i;
			mx=a[i].x;
			my=a[i].y;
		}
	}
	swap(a[1],a[x]);
	sort(a+2,a+n+1,cmp);
	k=1;
	s[1]=a[1];
	for (i=2;i<=n;i++)
	{
		while ((k>1) && (ar(s[k-1],s[k],a[i])<0))
			k--;
		s[++k]=a[i];
	}
	g << k << "\n";
	for (i=1;i<=k;i++)
		g << s[i].x << ' ' << s[i].y << "\n";
	return 0;
}