Cod sursa(job #1382967)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 9 martie 2015 19:43:33
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define NMax 120010

using namespace std;

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

int n, top;

struct mPoint
{
	double x;
	double y;
} points[NMax], stack[NMax];

double angle(const mPoint &p1, const mPoint &p2, const mPoint &p3)
{
	return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}

bool cmp(const mPoint &p1, const mPoint &p2)
{
	return angle(points[1], p1, p2) < 0;
}

int main()
{
	f >> n;
	for (int i = 1; i <= n; i++)
		f >> points[i].x >> points[i].y;

	int pos = 1;
	for (int i = 1; i <= n; i++) {
		if (points[i].x < points[pos].x || (points[i].x == points[pos].x && points[i].y < points[pos].y))
			pos = i;
	}
	swap(points[1], points[pos]);
	sort(points + 2, points + n + 1, cmp);

	stack[1] = points[1];
	stack[2] = points[2];
	top = 2;
	for (int i = 3; i <= n; i++) {
		while (top >= 2 && angle(stack[top - 1], stack[top], points[i]) > 0)
			top--;
		stack[++top] = points[i];
	}

	g << top << "\n";
	for (int i = top; i >= 1; i--)
		g << setprecision(9) << stack[i].x << " " << stack[i].y << "\n";
	return 0;
}