Cod sursa(job #3217376)

Utilizator BalanelBalan Stefan Balanel Data 22 martie 2024 16:56:40
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include<bits/stdc++.h>
#define int long long
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
typedef pair<double,double> pct;
int n;
pct v[120001];
double det(pct a, pct b, pct c) {
    return a.first*b.second+b.first*c.second+c.first*a.second-
    b.second*c.first-a.second*b.first-c.second*a.first;

}
bool comp(pct a, pct b) {
    return det(v[1],a,b)>0;
}
int32_t main()
{in>>n;
int mn=1;
for(int i=1;i<=n;++i) {
    in>>v[i].first>>v[i].second;
    mn=(v[i].first<v[mn].first || v[i].first==v[mn].first && v[i].second<v[mn].second) ? i : mn;
    }
swap(v[1],v[mn]);
sort(v+2,v+n+1,comp);
int k=2; v[n+1]=v[1];
for(int i=3;i<=n+1;++i) {
    while(k>=2 && det(v[k-1],v[k],v[i])<0)
        k--;
    v[++k]=v[i];
    }
out<<k-1<<'\n';
for(int i=1;i<k;++i)
    out<<fixed<<setprecision(6)<<v[i].first<<' '<<v[i].second<<'\n';
return 0;
}