Cod sursa(job #582521)

Utilizator nandoLicker Nandor nando Data 15 aprilie 2011 14:39:25
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 120010

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

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

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

bool sgn (int a, int b, int c)
{
    return (1LL * 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 = 0; 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 = 0; 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) {
        if (*it == pi)
            continue;

        while (sol.size () >= 2 && sgn (*(sol.end () - 2), *(sol.end () - 1), *it)) {
            sol.pop_back ();
        }

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

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

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

    fin.close ();
    return 0;
}