Cod sursa(job #834958)

Utilizator andreea29Iorga Andreea andreea29 Data 15 decembrie 2012 17:55:00
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include<fstream>
#include<algorithm>
#include<cmath>

#define Nmax 120010
#define Num 10000000

using namespace std;

int n, st[Nmax], viz[Nmax], k;

struct punct 
{
	float x;
	float y;
} p[Nmax];

int cmp (punct a, punct b)
{
	if (a.x > b.x || (a.x == b.x && a.y > b.y))
		return 0;
	return 1;
}

float dist (punct a, punct b)
{
	return sqrt (double ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)));
}

float det (punct a, punct b, punct c)
{
	return (a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x);
}

int semn (punct a, punct b, punct c)
{
	float d = det (a, b, c);
	if (d > 0)
		return 1;
	else
		if (d < 0)
			return 2;
		else
			return 0;
}

void convex ()
{
	st[0] = 0;
	st[1] = 1;
	st[2] = 2;
	viz[0] = viz[1] = viz[2] = 1;
	int s = semn (p[0], p[1], p[2]);
	k = 2;
	int i = 3;
	while (i < n)
	{
		int s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
		while (s != s1 && s1 != 0)
		{
			viz[st[k]] = 0;
			--k;
			s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
		}
		++k;
		st[k] = i;
		viz[i] = 1;
		++i;
	}
	--i;
	while (i >= 0)
	{
		while (viz[i])
			--i;
		int s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
		while (s != s1 && s1 != 0 && i >= 0)
		{
			--k;
			s1 = semn (p[st[k - 1]], p[st[k]], p[i]);
		}
		if (i >= 0)
		{
			++k;
			st[k] = i;
			--i;
		}
	}
}

int main()
{
	ifstream f("infasuratoare.in");
	ofstream h("infasuratoare.out");
	f >> n;
	for (int i = 0; i < n; ++i)
		f >> p[i].x >> p[i].y;
	f.close();
	sort (p, p + n, cmp);
	
	for (int i = 0; i < n; ++i)
//		h << p[i].x << " " << p[i].y << '\n';
//	h << '\n'<< '\n';
	
	convex ();
	
	h << k << '\n';
	for (int i = 0; i < k; ++i)
	{
		long long am = p[st[i]].x * Num;
		h << double (am / Num);
		h << " ";
		am = p[st[i]].y * Num;
		h << double (am / Num);
		h << '\n';
		//h << p[st[i]].x << " " << p[st[i]].y << '\n';
	}
	h.close();
	return 0;
}