Cod sursa(job #2586850)

Utilizator OvidRata Ovidiu Ovid Data 21 martie 2020 17:29:13
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 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;
pair<double, double> p[120000];



double cross_product(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);

}








int main(){
fin>>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;
}

}



vector<pair<double, int> > g;
vector<pair<double, double> > a;
g.pb(mp(-100, p0) );

for(int i=0; i<n; i++){
    if(i!=p0){
        g.pb( mp(atan2( (p[i].sc-p[p0].sc), (p[i].ft-p[p0].ft )   ), i)    );
        }
}

sort(g.begin(), g.end());




while(!g.empty()){
    a.pb( p[g[0].sc] ); g.erase(g.begin(), g.begin()+1 );
}


vector<pair<double, double>> h; h.pb(a[0]); h.pb(a[1]); h.pb(a[2]); a.erase(a.begin(), a.begin()+3);


while(!a.empty()){

if(cross_product(h[h.size()-3], h[h.size()-2], h[h.size()-1])<0  ){
    h.erase(h.end()-2, h.end()-1);
}

h.pb(a[0]);
a.erase(a.begin(), a.begin()+1);


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

return 0;
}