Cod sursa(job #2193578)

Utilizator PredaBossPreda Andrei PredaBoss Data 10 aprilie 2018 16:15:45
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
long double x,y;
long double px=1000000001;
long double py=1000000001;
struct elements
{
    long double first,second,third;
};
vector<pair<long double,long double> >rez;
vector<elements>elem;
long double make_unghi(elements a)
{
    long double unga;
    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)));
    return unga;
}
bool cmp(elements a,elements b)
{
    if(a.third==b.third)
        return a.first<b.first;
    return a.third<b.third;
}
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.pop_back();
        }
        h++;
        rez.push_back({elem[i].first,elem[i].second});
    }
    h+=2;
        fout<<fixed;
    fout<<setprecision(6);
    fout<<h<<"\n";
    for(int i=0;i<h;i++)
        fout<<rez[i].second<<" "<<rez[i].first<<"\n";
}
int main()
{
    fin>>n;
    int ind=0;
    for(int i=0;i<n;i++)
    {
        fin>>y>>x;
        elem.push_back({x,y,0});
        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());
    for(int i=0;i<n-1;i++)
        elem[i].third=make_unghi(elem[i]);
    sort(elem.begin(),elem.end(),cmp);
    infasuratoare();
    return 0;
}