Cod sursa(job #1144646)

Utilizator manutrutaEmanuel Truta manutruta Data 17 martie 2014 13:39:53
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
typedef vector<int>::iterator iter;

#define MAXN 120005

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

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

inline 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()
{
    f >> n;
    for (int i = 1; i <= n; i++) {
        f >> pt[i].first >> pt[i].second;

        if (pt[pi].first > pt[i].first || (pt[pi].first == pt[i].first && pt[pi].second > pt[i].second)) {
            pi = i;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (i != pi) {
            ind.push_back(i);
        }
    }

    sort(ind.begin(), ind.end(), cmp);

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

    g << sol.size() << '\n';
    for (iter it = sol.begin(); it != sol.end(); it++) {
        g << pt[*it].first << ' ' << pt[*it].second << '\n';
    }

    f.close();
    g.close();
    return 0;
}