Cod sursa(job #1846775)

Utilizator tudormaximTudor Maxim tudormaxim Data 14 ianuarie 2017 00:31:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;

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

const int maxn = 12e4 + 5;
int Stk[maxn], top;

struct Point {
    double x, y;
} P[maxn];

inline double Det (const Point& A, const Point& B, const Point& C) {
    return A.x * B.y + B.x * C.y + C.x * A.y - A.y * B.x - B.y * C.x - C.y * A.x;
}

inline bool Cmp (const Point& X, const Point& Y) {
    return Det(P[1], X, Y) > 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].x >> P[i].y;
        if (P[i].x < P[pos].x) {
            pos = i;
        }
        if (P[i].x == P[pos].x && P[i].y < P[pos].y) {
            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 && 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]].x << " " << P[Stk[i]].y << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}