Cod sursa(job #2267850)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 24 octombrie 2018 09:13:02
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
   
using namespace std;

typedef long long int ll;
typedef long double ld;
typedef pair < ld, ld > pld;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
   
vector < pld > v;

ld crossProduct(const pld &a, const pld &b, const pld &c) {
    return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
}

int main() {
    int n; fin >> n;
    
    v.resize(n);
    for (auto &x: v) fin >> x.first >> x.second;

    int pos = 0;
    for (int i = 1; i < n; ++i) {
        if (v[i].first < v[pos].first) {
            pos = i;
        }
    }
    swap(v[pos], v[0]);
    sort(v.begin() + 1, v.end(), [&](const pld &a, const pld &b) {
        return crossProduct(v[0], a, b) < 0.0;
    });

    vector < pld > A, B;
    A.push_back(v[0]);
    A.push_back(v[1]);
    for (int i = 2; i < n; ++i) {
        int top = (int)A.size();
        if(A.size() >= 2 && crossProduct(A[top - 2], A[top - 1], v[i]) > 0) {
            // B.push_back(A[top - 1]);
            A.pop_back();
            --top;
        }
        A.push_back(v[i]);
    }

    fout << (int)A.size() << "\n";
    for(auto x: A) {
        fout << fixed << setprecision(10) << x.first << " " << x.second << "\n";
    }
    return 0;
}