Cod sursa(job #3226684)

Utilizator Bianca2507Negret Bianca Bianca2507 Data 22 aprilie 2024 16:06:49
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n,s[120005],k,pmin;
pair<double,double>v[120005];
double det(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 det(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+2;
    v[0].second=1e9+2;
    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&&det(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;
}