Cod sursa(job #1920211)

Utilizator blatulInstitutul de Arta Gastronomica blatul Data 9 martie 2017 22:59:30
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

double Determinant(const pair<double, double>& a, const pair<double, double>& b, const pair<double, double>& c) {
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

int main() {
    #ifdef INFOARENA
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    #endif
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout.precision(12);
    cout.setf(ios::fixed, ios::floatfield);
    
    int n;
    cin >> n;
    
    vector<pair<double, double>> Points(n);
    for(auto &point : Points)
        cin >> point.x >> point.y;
        
    sort(begin(Points), end(Points));
    
    vector<int> LowerStk;
    for(int i = 0; i < (int)Points.size(); ++i) {
        int m = (int)LowerStk.size();
        while(m > 1 && Determinant(Points[LowerStk[m - 2]], Points[LowerStk[m - 1]], Points[i]) < 1e-12) {
            LowerStk.pop_back();
            m--;
        }
        
        LowerStk.push_back(i);
    }
    
    vector<int> UpperStk;
    for(int i = (int)Points.size() - 1; i >= 0; --i) {
        int m = (int)UpperStk.size();
        while(m > 1 && Determinant(Points[UpperStk[m - 2]], Points[UpperStk[m - 1]], Points[i]) < 1e-12) {
            UpperStk.pop_back();
            m--;
        }
        
        UpperStk.push_back(i);
    }
    
    LowerStk.pop_back();
    UpperStk.pop_back();
    
    cout << LowerStk.size() + UpperStk.size() << '\n';
    for(const int &a : LowerStk)
        cout << Points[a].x << ' ' << Points[a].y << '\n';
    
    for(const int& a : UpperStk)
        cout << Points[a].x << ' ' << Points[a].y << '\n';
}