Cod sursa(job #1668408)

Utilizator ArkinyStoica Alex Arkiny Data 29 martie 2016 19:39:27
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb

//JARVIS MARCH

#include<fstream>
#include<vector>
#include<iomanip>
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];

vector<POINT2D> vec;

double 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);
}


int main()
{
	in >> N;

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

	double y_min = v[1].y;
	int 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]);
	
	vec.push_back(v[1]);

	int i;

	for (i = 1;i <= N - 2;++i)
	{
		el = i + 1;
		for (int j = i + 2;j <= N;++j)
			if (crossprod2D(v[i], v[el], v[j]) < 0)
				el = j;
		swap(v[el], v[i + 1]);

		if (crossprod2D(v[i], v[i+1], v[1]) < 0)
			break;

		vec.push_back(v[i + 1]);
	}

	if (i == N - 1)
		vec.push_back(v[N]);

	out << vec.size() << '\n';

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