Cod sursa(job #2477652)

Utilizator cyber_ghSoltan Gheorghe cyber_gh Data 20 octombrie 2019 21:06:41
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 120010;
typedef pair<double, double> pdd;
const double eps = 1e-10;
vector<pdd> V(MAXN);
int N;
pdd firstPoint = {1e16, 1e16};
int firstPos = -1;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

vector<pdd> stk;

double cross(pdd a, pdd b, pdd c) {
    return (b.first - a.first) * (c.second - a.second) - (c.first - a.first) * (b.second - a.second);
}



int main() {
    fin >> N;
    V.resize(N);
    
    for (int i = 0; i < N; i++) {
        fin >> V[i].first >> V[i].second;
        if (V[i] < firstPoint) {
            firstPoint = V[i];
            firstPos = i;
        }
    }

    swap(V[0], V[firstPos]);
    //cout << firstPoint.first << " " << firstPoint.second << endl;

    sort(V.begin() + 1, V.end(), [](pdd a, pdd b) {
        return cross(firstPoint, a, b) < 0;
    });

    //cout << endl;
    //for (auto point : V) cout << point.first << " " << point.second << endl;

    stk.push_back(firstPoint);
    stk.push_back(V[1]);

    for (int i = 2; i < V.size(); i++) {
        pdd currPoint = V[i];
        while ((cross(stk[stk.size() - 2], stk[stk.size() - 1], currPoint) >= 0) && stk.size() > 2) stk.pop_back();

        stk.push_back(currPoint); 
    }
    fout << stk.size() << endl;
    reverse(stk.begin(), stk.end());
    for (auto point: stk) fout << fixed << setprecision(6) << point.first << " " << point.second << "\n";

    return 0;
}