Cod sursa(job #940801)

Utilizator forgetHow Si Yu forget Data 17 aprilie 2013 08:25:46
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

struct point
{
	double x, y;
	bool operator <(const point& a) const{
		return (x != a.x? x < a.x : y < a.y);
	}
};

bool ccw(point a, point b, point c)
{
	return (b.x-a.x)*(c.y-a.y) >= (c.x-a.x)*(b.y-a.y);
}

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

	int n;
	fin >> n;
	point p[n];
	for (int i = 0; i < n; ++i)
		fin >> p[i].x >> p[i].y;
	sort(p,p+n);

	vector<point> l, u;
	for (int i = n-1; i >= 0; --i) {
		while (u.size() >= 2)
			if (ccw(u[u.size()-2], u.back(), p[i])) break;
			else u.pop_back();
		u.push_back(p[i]);
	}
	for (int i = 0; i < n; ++i) {
		while (l.size() >= 2)
			if (ccw(l[l.size()-2], l.back(), p[i])) break;
			else l.pop_back();
		l.push_back(p[i]);
	}

	fout.precision(12);
	fout << u.size()+l.size()-2 << '\n';
	for (unsigned int i = 1; i < u.size(); ++i)
		fout << u[i].x << ' ' << u[i].y << '\n';
	for (unsigned int i = 1; i < l.size(); ++i)
		fout << l[i].x << ' ' << l[i].y << '\n';
	return 0;
}