Cod sursa(job #2657726)

Utilizator etienAndrone Stefan etien Data 11 octombrie 2020 19:51:41
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.26 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair<double,double>v[120001];
vector<pair<double,double>>up;
vector<pair<double,double>>down;
vector<pair<double,double>>sus;
vector<pair<double,double>>jos;
bool over(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-a.second*b.first-b.second*c.first-a.first*c.second>0;
}
int main()
{
    int n;
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>v[i].second>>v[i].first;
    }
    sort(v+1,v+n+1);
    for(int i=1;i<=n;i++)
    {
        swap(v[i].second,v[i].first);
    }
    up.push_back(v[1]);
    down.push_back(v[1]);
    for(int i=2;i<=n;i++)
    {
        if(over(v[1],v[n],v[i]))
            sus.push_back(v[i]);
        else jos.push_back(v[i]);
    }
    for(auto punct:sus)
    {
        if(up.size()==1)
            up.push_back(punct);
        else
        {
             pair<double,double>p2=*up.rbegin();
             up.pop_back();
             pair<double,double>p1=*up.rbegin();
             up.push_back(p2);
             while(up.size()>=2&&over(p1,p2,punct))
             {
                 up.pop_back();
                 p2=*up.rbegin();
                 up.pop_back();
                 p1=*up.rbegin();
                 up.push_back(p2);
             }
             up.push_back(punct);
        }
    }
    for(auto punct:jos)
    {
        if(down.size()==1)
            down.push_back(punct);
        else
        {
             pair<double,double>p2=*down.rbegin();
             down.pop_back();
             pair<double,double>p1=*down.rbegin();
             down.push_back(p2);
             while(down.size()>=2&&!over(p1,p2,punct))
             {
                 down.pop_back();
                 p2=*down.rbegin();
                 down.pop_back();
                 p1=*down.rbegin();
                 down.push_back(p2);
             }
             down.push_back(punct);
        }
    }
    fout<<fixed<<setprecision(12);
    for(auto punct:down)
        fout<<punct.first<<" "<<punct.second<<"\n";
    for(int i=up.size()-1;i>0;i--)
        fout<<up[i].first<<" "<<up[i].second<<"\n";

}