Cod sursa(job #1131324)

Utilizator manutrutaEmanuel Truta manutruta Data 28 februarie 2014 19:22:45
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

#define MAXN 120005
#define x first
#define y second

struct point {
    double x, y;
};
typedef vector<int>::iterator iter;
typedef vector<int>::reverse_iterator riter;

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

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

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

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

int main()
{
    f >> n;
    for (int i = 1; i <= n; i++) {
        f >> pt[i].x >> pt[i].y;

        if (pt[pi].x > pt[i].x || (pt[pi].x == pt[i].x && pt[pi].y > pt[i].y)) {
            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() > 1 && sgn(*(sol.end() - 2), *(sol.end() - 1), *it)) {
            sol.pop_back();
        }
        sol.push_back(*it);
    }

    g << sol.size() << '\n';
    for (riter it = sol.rbegin(); it != sol.rend(); it++) {
        g << pt[*it].x << ' ' << pt[*it].y << '\n';
    }

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