Cod sursa(job #1529106)

Utilizator AndreiIstetulAndrei Andrei AndreiIstetul Data 20 noiembrie 2015 15:34:38
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 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];

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[1], 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;
}

// http://informaticasite.ro/backtracking/352-permutari-iterativ.html