Cod sursa(job #582543)

Utilizator nandoLicker Nandor nando Data 15 aprilie 2011 15:30:06
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 120010

fstream fin ("infasuratoare.in", ios::in);

int n, pi = 1;
pair <double, double> pt[MAXN];
vector <int> ind, sol;
typedef vector <int>::iterator iter;

bool cmp (int a, int b)
{
    return (double)(pt[a].first - pt[pi].first) * (pt[b].second - pt[pi].second) < (double)(pt[b].first - pt[pi].first) * (pt[a].second - pt[pi].second);
}

bool sgn (int a, int b, int c)
{
    return ((long double)pt[a].first * pt[b].second + pt[b].first * pt[c].second + pt[c].first * pt[a].second - pt[a].second * pt[b].first - pt[b].second * pt[c].first - pt[c].second * pt[a].first) > 0;
}

int main ()
{
    fin >> n;

    for (int i = 1; i <= n; ++i) {
        fin >> pt[i].first >> pt[i].second;

        if ((pt[pi].first == pt[i].first) ? (pt[pi].second > pt[i].second) : (pt[pi].first > pt[i].first)) {
            pi = i;
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (i != pi) {
            ind.push_back (i);
        }
    }

    sort (ind.begin (), ind.end (), cmp);
    sol.push_back (pi);

    for (iter it = ind.begin (); it != ind.end (); ++it) {
        while (sol.size () >= 2 && sgn (*(sol.end () - 2), *(sol.end () - 1), *it)) {
            sol.pop_back ();
        }

        sol.push_back (*it);
    }
    freopen ("infasuratoare.out", "wt", stdout);

    sol.push_back (pi);
    reverse (sol.begin (), sol.end ());

    printf ("%d\n", sol.size () - 1);

    for (iter it = sol.begin (); it != sol.end () - 1; ++it) {
        printf ("%lf %lf\n", pt[*it].first, pt[*it].second);
    }

    fin.close ();
    return 0;
}