Cod sursa(job #2410188)

Utilizator PredaBossPreda Andrei PredaBoss Data 19 aprilie 2019 19:56:17
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>
#define ld long double
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,it;
ld x,y;
pair<ld,ld>elem[250005],ans[250005];
bool verify(int i)
{
    return (ans[it-2].first-elem[i].first)*(ans[it-1].second-elem[i].second)-(ans[it-2].second-elem[i].second)*(ans[it-1].first-elem[i].first)<0;
}
int main()
{
    fin>>n;
    for(int i=0;i<n;i++)
        fin>>elem[i].first>>elem[i].second;
    sort(elem,elem+n);
    reverse_copy(elem,elem+n-1,elem+n);
    for(int i=0;i<2*n-1;i++)
    {
        while(it>1 && verify(i))
            it--;
        ans[it++]=elem[i];
    }
    it--;
    fout<<setprecision(12)<<fixed;
    fout<<it<<"\n";
    for(int i=0;i<it;i++)
        fout<<ans[i].first<<" "<<ans[i].second<<"\n";
    return 0;
}