Cod sursa(job #2879805)

Utilizator MaraNNedelcu Mara MaraN Data 28 martie 2022 23:30:09
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.87 kb
#include <bits/stdc++.h>

using namespace std;

double arie (pair<double, double> A, pair<double, double> B, pair<double, double> C)
{
    return A.first*B.second + B.first*C.second + C.first*A.second - C.first*B.second - A.first*C.second - B.first*A.second;
}

bool cmp (pair<double, double> a, pair<double, double> b)
{
    return a.second < b.second;
}

pair<double, double> coord[120000];

int main()
{
    ifstream fin ("infasuratoare.in");
    ofstream fout ("infasuratoare.out");
    int n, i;
    fin >> n;
    pair<double, double> pmin, pmax;
    pmin.second = 1000000000;
    pmax.second = -1000000000;
    for (i = 0; i < n; i++)
    {
        fin >> coord[i].first >> coord[i].second;
        if (coord[i].second > pmax.second)
        {
            pmax.first = coord[i].first;
            pmax.second = coord[i].second;
        }
        if (coord[i].second < pmin.second)
        {
            pmin.first = coord[i].first;
            pmin.second = coord[i].second;
        }
    }
    vector<pair<double, double> > dreapta;
    vector<pair<double, double> > stanga;
    for (i = 0; i < n; i++)
    {
        if (coord[i] != pmax && coord[i] != pmin)
        {
            double aria = arie(pmin, pmax, coord[i]);
            if (aria < 0)
                dreapta.push_back(make_pair(coord[i].first, coord[i].second));
            else stanga.push_back(make_pair(coord[i].first, coord[i].second));
        }
    }
    sort(dreapta.begin(), dreapta.end(), cmp);
    sort(stanga.begin(), stanga.end(), cmp);
    int vf = 0;
    pair<double, double> stiv[120000];
    stiv[vf++] = pmin;
    stiv[vf++] = dreapta[0];
    for (i = 1; i < dreapta.size(); i++)
    {
        if ( arie(stiv[vf-2], stiv[vf-1], dreapta[i]) > 0 ) 
            stiv[vf++] = dreapta[i];
        else 
        {
            while (arie(stiv[vf-2], stiv[vf-1], dreapta[i]) < 0)
            { 
                vf--;
            }
            stiv[vf++] = dreapta[i];
        }
    }
    if (arie(stiv[vf-2], stiv[vf-1], pmax) < 0)
        vf--;
    stiv[vf++] = pmax;
    stiv[vf++] = stanga[stanga.size() - 1];
    for (i = stanga.size() -2; i >= 0; i--)
    {
        if ( arie(stiv[vf-2], stiv[vf-1], stanga[i]) > 0 )
            stiv[vf++] = stanga[i];
        else 
        {
            while (arie(stiv[vf-2], stiv[vf-1], stanga[i]) < 0)
            { 
                vf--;
            }
            stiv[vf++] = stanga[i];
        }
    }
    if (arie(stiv[vf-2], stiv[vf-1], pmin) < 0)
        vf--;
    int puncte = vf;
    fout << puncte << '\n';
    fout << setprecision(6) << fixed;
    for (i = 0; i < puncte; i++)
    {
        if (i == puncte - 1)
            fout << stiv[i].first << " " << stiv[i].second;
        else fout << stiv[i].first << " " << stiv[i].second << '\n';
    }
    fin.close();
    fout.close();

    return 0;
}