Cod sursa(job #883371)

Utilizator Rares95Rares Arnautu Rares95 Data 19 februarie 2013 22:52:15
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
# include <cstdio>
# include <fstream>
# include <algorithm>
# include <iomanip>
using namespace std;

ofstream g ("infasuratoare.out");
# define x first
# define y second

const int Nmax = 120005;
typedef pair<double, double> nod;

int n, nr;
nod v[Nmax], sol[Nmax];

double verif_convex(nod a, nod b, nod c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
 
int cmp(nod a, nod b) {
    return verif_convex(v[1], a, b) < 0;
}

void citire ()
{
	freopen ("infasuratoare.in", "r", stdin);
	scanf ("%d", &n);
	for (int i = 1; i <= n; ++i)
	{
		scanf ("%lf%lf", &v[i].x, &v[i].y);
	}
}

void afisare ()
{
	g << fixed;
	g << nr << '\n';
	for (int i = nr; i > 0; --i)
		g << setprecision(9) <<sol[i].x << ' ' << sol[i].y << '\n';
	g.close ();
}

void sortare () 
{
    int poz = 1;
    for (int i = 2; i <= n; ++i)
        if (v[i] < v[poz])
            poz = i;
    swap(v[1], v[poz]);
    sort(v + 2, v + n + 1, cmp);
}

void infasuratoare_convexa ()
{
	sortare ();
	sol[1] = v[1];
	sol[2] = v[2];
	nr = 2;
	for (int i = 3; i <= n; ++i)
	{
		while (verif_convex(sol[nr-1], sol[nr], v[i]) > 0)
            --nr;
        sol[++nr] = v[i];
	}
}

int main ()
{
	citire ();
	infasuratoare_convexa ();
	afisare ();
	return 0;
}