Cod sursa(job #3120501)

Utilizator Sho10Andrei Alexandru Sho10 Data 7 aprilie 2023 11:02:38
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 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=1000000007;
ld const PI=3.14159265359;
ll const MAX_N=3e5+5;
ld const EPS=0.00000001;
#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 sz(a) (int)a.size()
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n;
pair<ll,ll>a[200005];
ll cross(pair<ll,ll>o,pair<ll,ll>x,pair<ll,ll>y){
ll val=o.f*(x.s-y.s)+x.f*(y.s-o.s)+y.f*(o.s-x.s);
if(val<0){
    return -1;
}
if(val>0){
    return +1;
}
return 0;
}
bool cmp(pair<ll,ll>x,pair<ll,ll>y){
ll o=cross(a[0],x,y);
if(o==0){
    return (a[0].f-x.f)*(a[0].f-x.f)+(a[0].s-x.s)*(a[0].s-x.s)<(a[0].f-y.f)*(a[0].f-y.f)+(a[0].s-y.s)*(a[0].s-y.s);
}else {
return o<0;
}
}
bool idk(pair<ll,ll>x,pair<ll,ll>y,pair<ll,ll>z){
ll val=cross(x,y,z);
return val<0;
}
int32_t main(){
CODE_START;
#ifdef LOCAL
ifstream cin("input.txt");
#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;
}
ll head=n;
a[n].f=LINF;
a[n].s=LINF;
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&&idk(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<<a[it].f<<' '<<a[it].s<<endl;
}
}