Cod sursa(job #2192926)

Utilizator PredaBossPreda Andrei PredaBoss Data 7 aprilie 2018 18:29:28
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
double x,y;
double px=1000000001;
double py=1000000001;
vector<pair<double,double> >elem,rez;
bool cmp(pair<double,double>a,pair<double,double>b)
{
    double unga,ungb;
    if(py<a.second)
        unga=1.0*(a.first-px)/(1.0*sqrt(1.0*(a.first-px)*(a.first-px)+1.0*(a.second-py)*(a.second-py)));
    else
        unga=1+1.0*(py-a.second)/(1.0*sqrt(1.0*(a.first-px)*(a.first-px)+1.0*(py-a.second)*(py-a.second)));
    if(py<b.second)
        ungb=1.0*(b.first-px)/(1.0*sqrt(1.0*(b.first-px)*(b.first-px)+1.0*(b.second-py)*(b.second-py)));
    else
        ungb=1+1.0*(py-b.second)/(1.0*sqrt(1.0*(b.first-px)*(b.first-px)+1.0*(py-b.second)*(py-b.second)));
    if(unga==ungb)
        return a.first<b.first;
    return unga<ungb;
}
void infasuratoare()
{
    rez.push_back({px,py});
    rez.push_back({elem[0].first,elem[0].second});
    int k=-1;
    int h=0;
    if(py<elem[0].second)
        k=1;
    for(int i=1;i<n-1;i++)
    {
        while(k*(elem[i].first*(rez[h+1].second-rez[h].second)+rez[h+1].first*(rez[h].second-elem[i].second)+rez[h].first*(elem[i].second-rez[h+1].second))<=0)
        {
            h--;
            rez.erase(rez.end());
        }
        h++;
        rez.push_back({elem[i].first,elem[i].second});
    }
    h+=2;
    fout<<h<<"\n";
    for(int i=0;i<h;i++)
        fout<<rez[i].second<<" "<<rez[i].first<<"\n";
}
int main()
{
    fin>>n;
    fout<<fixed;
    fout<<setprecision(12);
    int ind=0;
    for(int i=0;i<n;i++)
    {
        fin>>y>>x;
        elem.push_back({x,y});
        if(x<px)
        {
            px=x;
            py=y;
            ind=i;
            continue;
        }
        if(x==px && py>y)
        {
            px=x;
            py=y;
            ind=i;
            continue;
        }
    }
    elem.erase(ind+elem.begin());
    sort(elem.begin(),elem.end(),cmp);
    infasuratoare();
    return 0;
}