Cod sursa(job #2587950)

Utilizator OvidRata Ovidiu Ovid Data 23 martie 2020 21:02:17
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
ifstream fin("infasuratoare.in"); ofstream fout("infasuratoare.out");



int n;
vector<pair<double, double> > p;



double cross_product( pair<double, double> &p1, pair<double, double> &p2, pair<double, double> &p3 ){

return (p2.ft-p1.ft)*(p3.sc-p2.sc)-(p3.ft-p2.ft)*(p2.sc-p1.sc);

}



bool e(pair<double, double> a, pair<double, double> b){
 return a.ft<b.ft || ( (a.ft==b.ft) && (a.sc<b.sc)   );

}




int main(){
fin>>n;
p.resize(n);
int p0=0;
for(int i=0; i<n; i++){
fin>>p[i].ft>>p[i].sc;
if(p[i].sc<p[p0].sc){
p0=i;
}
else{
    if(p[i].sc==p[p0].sc){
        if(p[i].ft<p[p0].ft){
            p0=i;
        }
    }
}

}





sort(p.begin(), p.end(), e);




for(int i=2; i<p.size(); i++){


    while( i>=2 && cross_product( p[i-2], p[i-1], p[i]    )<=0   ){
        p.erase(p.begin()+i-2+1, p.begin()+i-2+2 ); i--;
    }




}




fout<<p.size()<<"\n";
for(int i=0; i<p.size(); i++){
    fout<<fixed<<setprecision(9)<<p[i].ft<<" "<<p[i].sc<<"\n";
}

return 0;
}