Cod sursa(job #1368825)

Utilizator tinkyAndrei Ilisei tinky Data 2 martie 2015 20:11:41
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include<fstream>
#include<iomanip>
#include<algorithm>
#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;
	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, zz;
	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;
	sol[++k] = 2;
	//n++;
	p[n + 1] = p[1];
	for (i = 3; i <= n; i++)
	{
		while (!sens(p[sol[k - 1]], p[sol[k]], p[i]) && k>2)
			k--;
		sol[++k] = i;
	}
	out << k << '\n';
	i = k;
	for (k = 1; k <= i; k++)
		out << setprecision(20) << p[sol[k]].x << " " << setprecision(20) << p[sol[k]].y << '\n';

}