Cod sursa(job #1073242)

Utilizator tudorv96Tudor Varan tudorv96 Data 5 ianuarie 2014 20:25:38
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;

typedef pair <double, double> punct;
typedef vector <punct> poligon;

const int N = 12e5 + 5;

punct S[N], P[N];
int n, k;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

inline double cross(punct A, punct B, punct C) {
    return (B.first - A.first) * (C.second - A.second) - (C.first - A.first) * (B.second - A.second);
}

inline bool cmp (punct A, punct B) {
    return cross(P[0], A, B) < 0;
}

int main() {
    fin >> n;
    int pos = 0;
    for (int i = 0; i < n; ++i) {
        fin >> P[i].first >> P[i].second;
        if (P[pos] > P[i])
            pos = i;
    }
    swap (P[pos], P[0]);
    sort(P+1, P+n, cmp);
    S[k++] = P[0];
    S[k++] = P[1];
    for (int i = 2; i < n; ++i) {
        while (k > 1 && cross (S[k-2], S[k-1], P[i]) > 0)
            --k;
        S[k++] = P[i];
    }
    fout << fixed <<k << "\n";
    for (int i = k-1; i >= 0; --i)
        fout << setprecision(9) << S[i].first << " " << S[i].second << "\n";
    fout.close();
    return 0;
}