Cod sursa(job #2886812)

Utilizator Sho10Andrei Alexandru Sho10 Data 8 aprilie 2022 13:20:45
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho
using ll=long long;
using ld=long double;
int const INF=1000000005;
ll const LINF=1000000000000000005;
ll const mod=1e9+7;
ld const PI=3.14159265359;
ll const NMAX=3e6+5;
ld const eps=0.000001;
ll const block_size=250;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n;
pair<ld,ld>a[200005];
ld cross(pair<ld,ld>o,pair<ld,ld>b,pair<ld,ld>c){
b.f-=o.f;
b.s-=o.s;
c.f-=o.f;
c.s-=o.s;
return (b.f*c.s)-(b.s*c.f);
}
bool cmp(pair<ld,ld>x,pair<ld,ld>y){
return cross(a[0],x,y)>0;
}
int32_t main(){
CODE_START;
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin>>n;
for(ll i=0;i<n;i++)
{
    cin>>a[i].f>>a[i].s;
}
a[n]=mp(1e9,1e9);
ll head=n;
for(ll i=0;i<n;i++)
{
    if(a[i].s<a[head].s||(a[i].s==a[head].s&&a[i].f<a[head].f)){
        head=i;
    }
}
swap(a[0],a[head]);
sort(a+1,a+n,cmp);
vector<ll>st;
st.pb(0);
st.pb(1);
for(ll i=2;i<n;i++)
{
    while(st.size()>=2&&cross(a[st[st.size()-2]],a[st[st.size()-1]],a[i])<0){
        st.pop_back();
    }
    st.pb(i);
}
cout<<st.size()<<endl;
for(auto it : st){
    cout<<fixed<<setprecision(10)<<a[it].f<<' '<<a[it].s<<endl;
}
}