Cod sursa(job #2539211)

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

using namespace std;

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

pair <double, double> v[120005], stiva[120005];

int n, pmin, i, j, k;

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 (v[1].first, v[1].second, 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;
}



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[1] = v[1], stiva[2] = v[2], k = 2;
    for (i=3; i<=n; i++){
        while (k >= 2 && det (stiva[k-1].first, stiva[k-1].second, stiva[k].first, stiva[k].second, v[i].first, v[i].second) <= 0.0){
            k--;
        }
        stiva[++k] = v[i];
    }
    fout << k << "\n";
    for (i=1; i<=k; i++){
        fout << fixed << setprecision(6) << (int)1000000*stiva[i].first/1000000.0 << " " << (int)1000000*stiva[i].second/1000000.0 << "\n";
    }
    return 0;
}