Cod sursa(job #2881528)

Utilizator MaraNNedelcu Mara MaraN Data 30 martie 2022 15:55:30
Problema Infasuratoare convexa Scor 100
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)
{
    if (a.second == b.second)
        return a.first < b.first;
    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;
    pmin.first = 1000000000;
    pmax.second = -1000000000;
    pmax.first = -1000000000;
    for (i = 0; i < n; i++)
    {
        fin >> coord[i].first >> coord[i].second;
        if (cmp(coord[i], pmin))
        {
            pmin = coord[i];
        }
        if (!cmp(coord[i], pmax))
        {
            pmax = coord[i];
        }
    }
    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;
}