Cod sursa(job #1488621)

Utilizator lflorin29Florin Laiu lflorin29 Data 19 septembrie 2015 13:07:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

const int kPoints = 1 << 17;
const double eps = 1e-12;

int n, from;
int stk[kPoints];
bool use[kPoints];
pair <double, double> v[kPoints];

void Read() {
    ifstream fin ("infasuratoare.in");
    fin >> n;

    for (int i = 1; i <= n; ++i)
        fin >> v[i].first >> v[i].second;
}

double crossProd (const pair <double, double>& From, const pair <double, double> &a, const pair <double, double> &b) {
    return (a.first - From.first) * (b.second - From.second) - (b.first - From.first) * (a.second - From.second);
}

void Solve() {
    bool path = false;
    sort(v + 1, v + n + 1);
    from = 2;
    stk[1] = 1, stk[2] = 2;
    use[2] = true;

    for (int i = 1; i > 0 ; path |= i == n, i -= path ? 1 : -1 ) {
        if (use[i])
          continue;

        while (from >= 2 and crossProd(v[stk[from - 1]], v[stk[from]], v[i]) < eps)
             use[stk[from]] = false, --from;

        use[i] = true;
        stk[++from] = i;
    }
}

void Print() {
    ofstream fout ("infasuratoare.out");
    fout << from - 1 << fixed << setprecision(12) << "\n";

    for (int i = 1 ; i < from ; ++i)
        fout << v[stk[i]].first << " " << v[stk[i]].second << "\n";
}

int main() {
    Read();
    Solve();
    Print();
}