Cod sursa(job #2334259)

Utilizator victorv88Veltan Victor victorv88 Data 2 februarie 2019 14:07:05
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.25 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n;

struct p{
    double x, y;
}puncte[120005];

vector<int>s1,s2;

bool cmp(p a, p b)
{
    if (a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}

long double determinant(int ind1, int ind2, int ind3)
{
    return puncte[ind1].x*puncte[ind2].y+puncte[ind2].x*puncte[ind3].y+puncte[ind3].x*puncte[ind1].y-puncte[ind1].y*puncte[ind2].x-puncte[ind2].y*puncte[ind3].x-puncte[ind3].y*puncte[ind1].x;
}

void cautare_stanga()
{
    s1.push_back(1);
    for (int i=2; i<=n; ++i)
    {
        if (s1.size()==1)
        {
            s1.push_back(i);
        }
        else
        {
            long double val=determinant(s1[s1.size()-2],s1[s1.size()-1],i);
            if (val>=0)
            {
                s1.push_back(i);
            }
            else
            {
                s1.pop_back();
                while (s1.size()>1 && determinant(s1[s1.size()-2],s1[s1.size()-1],i)<=0)
                {
                    s1.pop_back();
                }
                s1.push_back(i);
            }
        }
    }
}

void cautare_dreapta()
{
    s2.push_back(n);
    for (int i=n-1; i>0; --i)
    {
        if (s2.size()==1)
        {
            s2.push_back(i);
        }
        else
        {
            if (determinant(s2[s2.size()-2],s2[s2.size()-1],i)>=0)
            {
                s2.push_back(i);
            }
            else
            {
                s2.pop_back();
                while (s2.size()>1 && determinant(s2[s2.size()-2],s2[s2.size()-1],i)<=0)
                {
                    s2.pop_back();
                }
                s2.push_back(i);
            }
        }
    }
}

int main() {
    f >> n;
    for (int i=1; i<=n; ++i)
    {
        f >> puncte[i].x >> puncte[i].y;
    }
    sort(puncte+1,puncte+n+1,cmp);
    cautare_stanga();
    cautare_dreapta();
    g << s1.size()+s2.size()-2 << '\n';
    for (auto &v:s1)
    {
        g <<setprecision(6)<<fixed<< puncte[v].x <<' ' << puncte[v].y <<'\n';
    }

    for (int i=1; i<s2.size()-1; i++)
    {
        g <<setprecision(6)<<fixed<< puncte[s2[i]].x <<' ' << puncte[s2[i]].y << '\n';
    }
    return 0;
}