Cod sursa(job #2589337)

Utilizator OvidRata Ovidiu Ovid Data 26 martie 2020 10:48:04
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 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;






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

}



double cp(pair<double, double> p1, pair<double, double> p2, pair<double, double> p3 ){

return (p2.ft-p1.ft)*(p3.sc-p1.sc)-(p3.ft-p1.ft)*(p2.sc-p1.sc);
// negativ-dreapta
//pozitiv-stanga
}







int main(){
fin>>n;
p.resize(n);

for(int i=0; i<n; i++){
fin>>p[i].ft>>p[i].sc;


}





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

pair<double, double> p1, p2;
p1=p.front(); p2=p.back();

vector<pair<double, double> > up, down;

up.pb(p1); down.pb(p1);


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

if( cp(p1, p[i], p2)<0 ){

while(up.size()>=2 && cp(up[up.size()-2 ], up[up.size()-1], p[i]  )>=0 ){
    up.pop_back();
}
up.pb(p[i]);  continue;
}

if(cp(p1, p[i], p2)>0  ){

    while(down.size()>=2 && cp(down[down.size()-2], down[down.size()-1], p[i] )<=0 ){
        down.pop_back();
    }
    down.pb(p[i]);

}



}

while(up.size()>=2 && cp(up[up.size()-2 ], up[up.size()-1], p2  )>=0 ){
    up.pop_back();
}


    while(down.size()>=2 && cp(down[down.size()-2], down[down.size()-1], p2 )<=0 ){
        down.pop_back();
    }



fout<<max( (int)down.size(), 1)-1+max( (int)up.size(),1 )-1+2<<"\n";
fout<<fixed<<setprecision(9)<<p1.ft<<" "<<p1.sc<<"\n";

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

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




return 0;
}