Cod sursa(job #1553836)

Utilizator Vladut-Vlad Panait Vladut- Data 20 decembrie 2015 16:28:32
Problema Infasuratoare convexa Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#define NMAX 1200050

using namespace std;

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

struct point
{
	double x;
	double y;
	point()
	{
		this->x = 0;
		this->y = 0;
	}
	point(double x, double y)
	{
		this->x = x;
		this->y = y;
	}
	//point(const point &P)
	//{
	//	this->x = P.x;
	//	this->y = P.y;
	//}
	bool operator<(point &P)
	{
		return(this->x < P.x || (!(this->x < P.x) && this->y < P.y));
	}
	friend istream &operator>>(istream &stream, point& P);
	friend ostream &operator<<(ostream &stream, point& P);
};

istream &operator>>(istream &stream, point &P)
{
	stream >> P.x >> P.y;
	return stream;
}

ostream &operator<<(ostream &stream, point &P)
{
	stream  <<  P.x << " " << P.y << "\n";
	return stream;
}

point V[NMAX];
int N;

point vect(const point &P1, const point &P2)
{
	return point(P2.x - P1.x, P2.y - P1.y);
}

double cross_product(const point &P1, const point &P2, const point &P3)
{
	point A, B;
	A=vect(P1, P2);
	B=vect(P1, P3);
	return (A.x*B.y - A.y*B.x);
}

bool cmp(const point &P1, const point &P2)
{
	return (cross_product(V[1], P1, P2) < 0)? 1 : 0;
}

void _sort()
{
	int poz = 1;
	for (int i = 2; i <= N; i++)
	{
		if (V[i] < V[poz])
		{
			poz = i;
		}
		swap(V[1], V[poz]);
	}
	sort(V + 2, V + N + 1, cmp);
}

vector<point> convex_hull()
{
	vector<point> st;
	_sort();
	st.push_back(V[1]);
	st.push_back(V[2]);
	for (int i = 3; i <= N; i++)
	{
		while (st.size() > 1 && cross_product(st[st.size() - 2], st[st.size() - 1], V[i]) > 0)
		{
			st.pop_back();
		}
		st.push_back(V[i]);

	}
	return st;
}

int main()
{
	point P;
	fin >> N;
	for (int i = 1; i <= N; i++)
	{
		fin >> P;
		V[i] = P;
	}
	vector<point> sol;
	sol = convex_hull();


	_sort();
	fout << sol.size() << '\n';
	fout << fixed;
	fout << setprecision(6);
	for (int i = sol.size() - 1; i >= 0; i--)
	{
		fout << sol[i];
	}



	return 0;
}