Cod sursa(job #2144601)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 26 februarie 2018 20:27:05
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iomanip>
#define EPSILON 1e-12

using namespace std;
vector <pair<double,double>> p;
vector <pair<double,double>> sol;
int n;
double a,b;
bool cmp(pair<double,double> a, pair<double,double> b)
{
    return (a.first<b.first) || (a.first<b.first && a.second<b.second);
}
double det(pair<double,double> a, pair<double,double> b, pair<double,double> c)
{
    return (a.first-b.first)*(a.second-c.second)-(a.second-b.second)*(a.first-c.first);
}
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>a>>b;
        p.push_back({a,b});
    }
    sort(p.begin(),p.end(),cmp);
    sol.push_back(p[0]);
    sol.push_back(p[n-1]);
    int l=1;
    for(int i=n-2;i>0;--i)
    {
        while(sol.size()>2 && det(sol[l-1],sol[l],p[i])<EPSILON)
        {
            --l;
            sol.pop_back();
        }
        ++l;
        sol.push_back(p[i]);
    }
    cout<<sol.size()<<"\n";
    cout<<fixed<<setprecision(6);
    for(auto i:sol)
        cout<<i.first<<" "<<i.second<<"\n";
    return 0;
}