Cod sursa(job #1529090)

Utilizator AndreiIstetulAndrei Andrei AndreiIstetul Data 20 noiembrie 2015 15:23:54
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

struct pair
{
	double x, y;

	 friend bool operator<  (const pair& lhs, const pair& rhs)
{ return lhs.x<rhs.x || (!(rhs.x<lhs.x) && lhs.y<rhs.y); }
};
int n, top, pos, s[120010];
pair v[120010], aux;

std::fstream in, out;

double det(pair a, pair b, pair c)
{
	return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

bool cmp(pair a, pair b)
{
	return (det(v[0], a, b) < 0);
}

int main(int argc, char *argv[])
{
	in.open("infasuratoare.in", std::fstream::in);
	out.open("infasuratoare.out", std::fstream::out);

	in >> n;
	pos = 1;

	for (int i = 1; i <= n; ++i)
	{
		in >> v[i].x >> v[i].y;
		if (v[i] < v[pos]) pos = i;
	}

	std::swap(v[1], v[pos]);
	std::sort(v + 2, v + n + 1, cmp);

    s[++top] = 1;
	for (int i = 2; i <= n; ++i)
    {
        while (top > 1 && det(v[s[top - 1]], v[s[top]], v[i]) > 0) --top;
        s[++top] = i;
    }

    out << top << "\n";
    while (top)
    {
        out << std::fixed << std::setprecision(6) << v[s[top]].x << ' ' << v[s[top]].y << "\n";
        --top;
    }

	return 0;
}