Cod sursa(job #1919315)

Utilizator tudormaximTudor Maxim tudormaxim Data 9 martie 2017 18:49:00
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

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

const int maxn = 12e4 + 5;
pair <double,double> P[maxn];
int Stk[maxn], top;

inline double Det (pair <double,double> A, pair <double,double> B, pair <double,double> C) {
    return A.first * B.second + B.first * C.second + C.first * A.second - A.second * B.first - B.second * C.first - C.second * A.first;
}

inline bool Cmp (pair <double,double> A, pair <double,double> B) {
    return Det (P[1], A, B) > 0;
}

int main() {
    ios_base :: sync_with_stdio (false);
    int n, i, pos = 1;
    fin >> n;
    for (i = 1; i <= n; i++) {
        fin >> P[i].first >> P[i].second;
        if (P[i].first < P[pos].first) {
            pos = i;
        } else if (P[i].first == P[pos].first && P[i].second < P[pos].second) {
            pos = i;
        }
    }
    swap(P[1], P[pos]);
    sort(P + 2, P + n + 1, Cmp);
    P[n + 1] = P[1];
    Stk[++top] = 1;
    for (i = 2; i <= n; i++) {
        Stk[++top] = i;
        while (top > 0 && Det(P[Stk[top - 1]], P[Stk[top]], P[i + 1]) < 0) {
            top--;
        }
    }
    fout << fixed << setprecision(6) << top << "\n";
    for (i = 1; i <= top; i++) {
        fout << P[Stk[i]].first << " " << P[Stk[i]].second << "\n";
    }
    return 0;
}