Cod sursa(job #2093074)

Utilizator HumikoPostu Alexandru Humiko Data 22 decembrie 2017 21:15:27
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <bits/stdc++.h>

using namespace std;

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

pair <long double, long double> v[120001];
vector<pair <long double, long double>> sol;

int cmp ( const pair <long double, long double> a, const pair <long double, long double> b)
{
    return (a.second/a.first)<(b.second/b.first);
}

long double determinant (long double x_1, long double y_1, long double x_2, long double y_2, long double x_3, long double y_3 )
{
    return x_1*y_2+x_2*y_3+x_3*y_1-y_1*x_2-y_2*x_3-y_3*x_1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n;
    fin>>n;
    fin>>v[0].first>>v[0].second;
    for ( int i = 1; i < n; ++i )
    {
        fin>>v[i].first>>v[i].second;
        if ( v[i].first < v[0].first || (v[0].first == v[i].first && v[i].second < v[0].second ) )
            swap (v[i], v[0]);
    }
    v[n] = v[0];
    sort (v+1, v+n, cmp);
    sol.push_back(v[0]);
    for ( int i = 1; i <= n; ++i )
    {
        bool prost = true;
        while ( sol.size() >= 2 && prost )
        {
            prost = false;
            pair < long double, long double > a = sol.back();
            sol.pop_back();
            if ( determinant (sol.back().first, sol.back().second, a.first, a.second, v[i].first, v[i].second) <= 0 ) prost = true;
            else sol.push_back(a);
        }
        sol.push_back(v[i]);
    }
    sol.pop_back();
    fout<<sol.size()<<'\n';
    for ( int i = 0; i < sol.size(); ++i )
        fout<<fixed<<setprecision(6)<<sol[i].first<<" "<<sol[i].second<<'\n';
}