Cod sursa(job #1414904)

Utilizator irimiecIrimie Catalin irimiec Data 3 aprilie 2015 12:02:51
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <bits/stdc++.h>

using namespace std;

#define     mp              make_pair
#define     fs              first
#define     sc              second
#define     pob             pop_back
#define     pub             push_back
#define     eps             1E-7
#define     sz(a)           a.size()
#define     count_one       __builtin_popcount;
#define     count_onell     __builtin_popcountll;
#define     fastIO          ios_base::sync_with_stdio(false)
#define     PI              (acos(-1.0))
#define     linf            (1LL<<62)//>4e18
#define     inf             (0x7f7f7f7f)//>2e9

#ifndef ONLINE_JUDGE
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#endif

const int MAXN = 120010;

int n, head;
pair<double, double> v[MAXN];
pair<double, double> res[MAXN];

inline double pantaComp(const pair<double, double> &A, const pair<double, double> &B, const pair<double, double> &C) {
    return (B.fs - A.fs) * (C.sc - A.sc) - (C.fs - A.fs) * (B.sc - A.sc);
}

inline int comp (const pair<double, double> &A, const pair<double, double> &B) {
        return pantaComp(v[1], A, B) < 0;
}

void read() {
    fin >> n;
    int x, y;
    int minpos = 1;
    for(int i = 1; i <= n; ++i) {
        fin >> v[i].fs >> v[i].sc;
        if(v[i].fs < v[minpos].fs)
            minpos = i;
    }
    swap(v[minpos], v[1]);
}

int main() {
	read();
    sort(v + 2, v + n + 1, comp);


    res[1] = v[1];
    res[2] = v[2];
    head = 2;
    for(int i = 3; i <= n; ++i) {
        while(head >= 2 && pantaComp(res[head - 1], res[head], v[i]) > 0)
              --head;
        res[++head] = v[i];
    }

    fout << head << "\n";
    for(int i = head; i; --i) {
        fout << fixed << setprecision(9) << res[i].fs << " " << res[i].sc << "\n";
    }
    return 0;
}