Cod sursa(job #2659656)

Utilizator CalinusCalin Navadaru Calinus Data 17 octombrie 2020 11:48:58
Problema Infasuratoare convexa Scor 70
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 > a.x)

            return 0;



        return 1;

    }

    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 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, 0, 0);

    afisare(v2, 1, 1);

    return 0;
}