Cod sursa(job #2394145)

Utilizator Ioana_GaborGabor Ioana Ioana_Gabor Data 1 aprilie 2019 12:44:08
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.19 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <stack>
#define NMAX  120000
#define VMAX 1000000000

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n,start,minx=VMAX+1,miny=VMAX+1,indici[NMAX+5],i1,i2,rez[NMAX+5],nrez;
pair <double,double> puncte[NMAX+5];
double c1,c2,c3,c4;
stack <int> stiva;

bool criteriu(int a,int b){
    if(a==start){
        return true;
    }else if(b==start){
        return false;
    }
    c1=puncte[a].first-puncte[start].first;
    c2=puncte[b].first-puncte[start].first;
    c3=puncte[a].second-puncte[start].second;
    c4=puncte[b].second-puncte[start].second;
    if(c1<=0&&c2>=0){
        return false;
    }else if(c1>=0&&c2<=0){
        return true;
    }else if(c1>0&&c2>0){
        return c1*c1*(c2*c2+c4*c4)>c2*c2*(c1*c1+c3*c3);
    }else{
        return c1*c1*(c2*c2+c4*c4)<c2*c2*(c1*c1+c3*c3);
    }
}

bool ok(int i){
    return (puncte[i1].first*puncte[i2].second+puncte[i2].first*puncte[i].second+puncte[i].first*puncte[i1].second-puncte[i].first*puncte[i2].second-puncte[i].second*puncte[i1].first-puncte[i2].first*puncte[i1].second)>0;
}

int main() {
    f>>n;
    for(int i=1;i<=n;i++){
        f>>puncte[i].first>>puncte[i].second;
        if(puncte[i].second<miny){
            miny=puncte[i].second;
            minx=puncte[i].first;
            start=i;
        }else if(puncte[i].second==miny&&minx>puncte[i].first){
            minx=puncte[i].first;
            start=i;
        }
        indici[i]=i;
    }
    sort(indici+1,indici+n+1,criteriu);
    indici[n+1]=start;
    stiva.push(start);
    stiva.push(indici[2]);
    for(int i=3;i<=n+1;i++){
        i2=stiva.top();
        stiva.pop();
        i1=stiva.top();
        if(ok(indici[i])){
            stiva.push(i2);
        }
        stiva.push(indici[i]);
    }
    while(!stiva.empty()){
        rez[++nrez]=stiva.top();
        stiva.pop();
    }
    nrez--;
    g<<nrez<<'\n';
    for(int i=nrez+1;i>=2;i--){
        g<<fixed<<setprecision(12)<<puncte[rez[i]].first<<' '<<puncte[rez[i]].second<<'\n';
    }
    f.close();
    g.close();
    return 0;
}