Cod sursa(job #2539181)

Utilizator radugheoRadu Mihai Gheorghe radugheo Data 5 februarie 2020 18:46:00
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <bits/stdc++.h>

using namespace std;

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

double det (double x1, double y1, double x2, double y2, double x3, double y3) {
    return (x2 - x1)*(y3 - y1) - (x3 - x1)*(y2 - y1);
}

double cmp (const pair<double, double> &a, const pair<double, double> &b) {
     double d = det (0, 0, a.first, a.second, b.first, b.second);
     if (d != 0)
        return d > 0;
     else
        return a.first*a.first + a.second*a.second > b.first*b.first + b.second*b.second;
}

pair <double, double> v[120005], top1, top2;

stack <pair<double, double> > stiva;

int n, pmin, i, j;

int main(){
    fin >> n;
    v[0] = {INT_MAX, INT_MAX};
    for (i=1; i<=n; i++){
        fin >> v[i].first >> v[i].second;
        if (v[i].second < v[pmin].second || (v[i].second == v[pmin].second && v[i].first < v[pmin].first)){
            pmin = i;
        }
    }
    v[0] = v[pmin], v[pmin] = v[1], v[1] = v[0];
    sort (v + 2, v + n + 1, cmp);
    for (j=3; j<=n; j++){
        if (det (v[1].first, v[1].second, v[2].first, v[2].second, v[j].first, v[j].second) != 0.0){
            break;
        }
    }
    i = 2, j--;
    while (i < j){
        swap (v[i], v[j]);
        i++, j--;
    }
    stiva.push (v[2]);
    top2 = v[2];
    stiva.push (v[1]);
    top1 = v[1];
    for (i=3; i<=n; i++){
        while (stiva.size() >= 2 && det (top2.first, top2.second, top1.first, top1.second, v[i].first, v[i].second) <= 0.0){
            top1 = stiva.top();
            stiva.pop();
            top2 = stiva.top();
        }
        stiva.push (v[i]);
    }
    fout << stiva.size() << "\n";
    while (!stiva.empty()){
        fout << fixed<<setprecision(6) << (int)1000000*stiva.top().first/1000000.0 << " " << (int)1000000*stiva.top().second/1000000.0 << "\n";
        stiva.pop();
    }
    return 0;
}