Cod sursa(job #1668487)

Utilizator ArkinyStoica Alex Arkiny Data 29 martie 2016 20:19:33
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb

//GRAHAM SCAN

#include<fstream>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<stack>

using namespace std;

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

int N;

typedef pair<double, double> POINT2D;

#define x first
#define y second

POINT2D v[120010];
POINT2D vec[120010];

int nr = 0;

int el = 1;

double inline crossprod2D(const POINT2D &p1, const POINT2D &p2, const POINT2D &p3)
{
	return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
}

bool compare(const POINT2D &p1, const POINT2D &p2)
{
	if (crossprod2D(v[1],p1,p2) > 0)
		return 1;
	else
		return 0;
}

int main()
{
	in >> N;

	for (int i = 1;i <= N;++i)
		in >> v[i].x >> v[i].y;

	double y_min = v[1].y;
	el = 1;
	for (int i = 2;i <= N;++i)
		if (v[i].y < y_min)
		{
			el = i;
			y_min = v[i].y;
		}
	swap(v[el], v[1]);

	sort(v + 2, v + N + 1, compare);
	
	vec[++nr] = v[1];
	vec[++nr] = v[2];



	for (int i = 3;i <= N;++i)
	{
		while (crossprod2D(vec[nr - 1], vec[nr], v[i]) < 0)
			--nr;

		vec[++nr] = v[i];
	}

	while (crossprod2D(vec[nr - 1], vec[nr], v[1]) < 0)
		--nr;

	out << nr << '\n';

	for (int i = 1;i <= nr;++i)
		out <<setprecision(12)<<fixed<< vec[i].x << " " << vec[i].y << '\n';
}