Cod sursa(job #724378)

Utilizator mottyMatei-Dan Epure motty Data 26 martie 2012 14:57:18
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

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

struct point {
	double x;
	double y;
};

vector <point> p;
vector <point> q;

void read() {
	int n;
	in >> n;

	while (n--) {
		point P;
		in >> P.x >> P.y;

		p.push_back(P);
	}
}

inline bool comp(point P, point Q) {
	if (P.x == Q.x)
		return (P.y < Q.y);
	return (P.x < Q.x);
}

inline bool turnsRight(point a, point b, point c) {
	double baz = a.x * b.y + c.x * a.y + b.x * c.y;
	baz -= a.x * c.y + c.x * b.y + b.x * a.y;

	return (baz > 0);
}

void addToStack(point x) {
	while (q.size() > 1 && turnsRight(q[q.size() - 2], q[q.size() - 1], x))
		q.pop_back();
	q.push_back(x);
}

void solve() {
	q.push_back(p[0]);

	for (int i = 1; i < (int)p.size(); ++i)
		addToStack(p[i]);

	for (int i  = p.size() - 2; i >= 0; --i)
		addToStack(p[i]);

	q.pop_back();
}

void print()
{
	out << q.size() << "\n";

	for (int i = q.size() - 1; i >= 0; --i)
		out << q[i].x/1.0 << " " << q[i].y/1.0 << "\n";
}

int main() {
	read();

	sort(p.begin(), p.end(), comp);
	solve();

	print();

	return 0;
}