Cod sursa(job #2659634)

Utilizator CalinusCalin Navadaru Calinus Data 17 octombrie 2020 11:29:31
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.17 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)
{
    for(unsigned int i = start; i < v.size(); 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();
    if(v1.size() < v2.size())
    {
        fout << v1.size() + v2.size() - 2 << '\n';
        afisare(v1, 1);
        afisare(v2, 1);
    }
    else
    {
        fout << v1.size() + v2.size() - 2 << '\n';
        afisare(v2, 1);
        afisare(v1, 1);
    }

    return 0;
}