Cod sursa(job #2659680)

Utilizator CalinusCalin Navadaru Calinus Data 17 octombrie 2020 12:02:30
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.22 kb
#include <fstream>

#include <iostream>

#include <vector>

#include <algorithm>

#include <iomanip>

using namespace std;



ifstream fin("infasuratoare.in");

ofstream fout("infasuratoare.out");



struct Punct

{

    double x;

    double y;

}puncte[120001];



int n;



vector<Punct>v1;

vector<Punct>v2;



bool cmp(Punct a, Punct b)

{

    if(a.x == b.x)

    {

        if(a.y < b.y)
            return 1;

        return 0;

    }

    if(a.x < b.x)
        return 1;

    return 0;

}



void citire()

{

    fin >> n;

    for(int i = 0; i < n; i++)

        fin >> puncte[i].x >> puncte[i].y;



    sort(puncte, puncte + n, cmp);

}



double det(Punct a, Punct b, Punct c)

{

    return double(a.x*b.y + b.x*c.y + a.y*c.x - a.x*c.y - c.x*b.y - b.x*a.y);

}



void rezolvare_prima_juma()

{

    v1.push_back(puncte[0]);

    v1.push_back(puncte[1]);

    for(int i = 2; i < n; i++)

    {

        if(v1.size() == 1)

            v1.push_back(puncte[i]);

        else

        {

            while(v1.size() > 1 && det(v1[v1.size() - 2], v1[v1.size() - 1], puncte[i]) <= 0)

                v1.pop_back();

            v1.push_back(puncte[i]);

        }

    }

}



void rezolvare_a_doua_juma()

{

    v2.push_back(puncte[n - 1]);

    v2.push_back(puncte[n - 2]);

    for(int i = n - 3; i >= 0; i--)

    {

        if(v2.size() == 1)

            v2.push_back(puncte[i]);

        else

        {

            while(v2.size() > 1 && det(v2[v2.size() - 2], v2[v2.size() - 1], puncte[i]) <= 0)

                v2.pop_back();

            v2.push_back(puncte[i]);

        }

    }

}



void afisare(vector<Punct> v, int start, int limita)

{

    for(unsigned int i = start; i < v.size() - limita; i++)

    {

        fout << fixed << setprecision(6) << v[i].x << ' ';

        fout << fixed << setprecision(6) << v[i].y << '\n';

    }

}



int main()

{

    citire();

    rezolvare_prima_juma();

    rezolvare_a_doua_juma();

    fout << v1.size() + v2.size() - 2 << '\n';

    afisare(v1, 1, 0);

    afisare(v2, 1, 0);

    return 0;
}