Cod sursa(job #2947541)

Utilizator OvidRata Ovidiu Ovid Data 26 noiembrie 2022 11:45:23
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.89 kb
#include<bits/stdc++.h>
using namespace std;

string numeFisier="infasuratoare";
ifstream fin(numeFisier+".in"); ofstream fout(numeFisier+".out");
#define cin fin
#define cout fout

#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
//#define int ll


int n;
pair<double, double> pr[120010];

double prod( pair<double, double> v1, pair<double, double> v2){
    return v1.ft*v2.sc-v2.ft*v1.sc;
}

bool is_conv(pair<double, double> p1, pair<double, double> p2, pair<double, double> p3){

if( prod( make_pair( p2.ft-p1.ft, p2.sc-p1.sc  ), make_pair( p3.ft-p1.ft, p3.sc-p1.sc )  )>=( (double) 0.000 ) ){
    return true;
}
return false;
}



vector<pair<double, double>> getConvexHull(pair<double, double> pr[], int n){

sort(pr+1, pr+1+n);


vector<pair<double, double>> hull;
for(int i=1; i<=n; i++){
    if(hull.size()<2){
        hull.pb(pr[i]);
        continue;
    }
    while( (hull.size()>=2) && (!is_conv( hull[hull.size()-2 ], hull[ hull.size()-1 ], pr[i] ) ) ){
        hull.pop_back();
    }
    hull.pb(pr[i]);
}


for(int i=n-1; i>=1; i--){
    if(hull.size()<2){
        hull.pb(pr[i]);
        continue;
    }
    while( (hull.size()>=2) && (!is_conv( hull[hull.size()-2 ], hull[ hull.size()-1 ], pr[i] ) ) ){
        hull.pop_back();
    }
    hull.pb(pr[i]);
}

hull.pop_back();


return hull;

}




int32_t main(){
INIT
cin>>n;
for(int i=1; i<=n; i++){
    cin>>pr[i].ft>>pr[i].sc;
}


vector<pair<double, double>> hull = getConvexHull(pr, n);

cout<<hull.size()<<"\n";
for(auto pr:hull){
    cout<<fixed<<setprecision(6)<<pr.ft<<" "<<pr.sc<<"\n";
}

return 0;
}