Cod sursa(job #3217289)

Utilizator Bianca2507Negret Bianca Bianca2507 Data 22 martie 2024 10:20:59
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n,pmin,k;
int s[120005];
pair<double,double>v[120005];

double panta(double x1,double y1,double x2,double y2,double x3,double y3)
{
    return (x2-x1)*(y3-y1)-(y2-y1)*(x3-x1);
}

int cmp(pair<double,double> a,pair<double,double>b)
{
    return panta(v[1].first,v[1].second,a.first,a.second,b.first,b.second)<0;
}

int main()
{
    cin>>n;
    pmin=0;
    v[0].first=1e9+1;
    v[0].second=1e9+1;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i].first>>v[i].second;
        if(v[i].first<v[pmin].first)
            pmin=i;
        else
            if(v[i].first==v[pmin].first&&v[i].second<v[pmin].second)
            pmin=i;
    }
    swap(v[1],v[pmin]);
    sort(v+2,v+n+1,cmp);
    s[1]=1;
    s[2]=2;
    k=2;
    for(int i=3;i<=n;i++)
    {
        while(k>2&&panta(v[s[k-1]].first,v[s[k-1]].second,v[s[k]].first,v[s[k]].second,v[i].first,v[i].second)>0)
            k--;
        s[++k]=i;
    }
    cout<<k<<'\n';

    for(int i=k;i>=1;i--)
        cout<<fixed<<setprecision(6)<<v[s[i]].first<<" "<<v[s[i]].second<<'\n';
    return 0;
}