Cod sursa(job #800807)

Utilizator vendettaSalajan Razvan vendetta Data 22 octombrie 2012 18:34:03
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
#include <iomanip>

using namespace std;

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

#define nmax 120005
#define Eps 0.000000000001
#define ll long long
#define inf (1<<29)

int n, poz;
pair<double, double> pct_init, v[nmax];
vector<int> puncte, a;

double modul(double X ){

    if (X < 0.000000000000){
        X = X * -1.00000000000;
    }

    return X;

}

bool cmp(int i, int j){

    //am punctele i, si j, si pct_initial(ala initial)
    //primul e mai "mic" fata de al doilea daca ( (x1 - X) / (y1-Y) ) < ( (x2 - X) / (y2 - Y) ); => pt a evita impartirea
    // = > (x1 - x) * (y2 - y) < (y1 - y) * (x2 - x);

    double x1 = v[i].first; double y1 = v[i].second;
    double x2 = v[j].first; double y2 = v[j].second;
    double X = pct_init.first; double Y = pct_init.second;

    if ( (x1-X) * (y2-Y) < (y1 - Y) * (x2 - X) ) return 1;
    return 0;

}

void citeste(){

    f >> n;
   double x,y;
      f >> x >> y;
      v[1] = make_pair(x,y);
      pct_init = make_pair(x,y);
    for(int i=2; i<=n; ++i){
   x, y;
        f >> x >> y;
        v[i] = make_pair(x, y);
        if (x < pct_init.first){
            pct_init = make_pair(x, y);
            poz = i;
        }
        else if ( modul( x - pct_init.first ) <= Eps ){//daca x-ul e egal; ma uit la y(imi trebuie cel mai din stanga si cel mai de jos
                if (y < pct_init.second){
                    pct_init = make_pair(x, y);
                    poz = i;
                }
            }
    }

    //le sortez pe celelalte in functie de punctul initial;
    for(int i=1; i<=n; ++i){
        if (i == poz) continue;//daca e punctul ala initial nu il mai sortez
        puncte.push_back( i );//bag doar pozitiile in vectorul initial;
    }

    sort(puncte.begin(), puncte.end(), cmp);

}

double semn( int i, int j, int k ){

    double x1 = v[i].first; double y1 = v[i].second;
    double x2 = v[j].first; double y2 = v[j].second;
    double x3 = v[k].first; double y3 = v[k].second;
    //acum aflu determinantul lui :
    //x1 y1 1
    //x2 y2 1
    //x3 y3 1
    //daca il explicitez o sa am x1*(y2-y3) + y1*(x3-x2) + x2*y3 - x3 * y2;
    double c = x2*y3 - x3*y2;
    return ( x1*(y2-y3) + y1*(x3-x2) + c );

}

void rezolva(){

    //fac cu scanarea graham; imi aleg cel mai din sanga jos puncte dintre cele n (asta sigur face parte din infasuratoare) apoi le sortez pe restul
    //in functie de panta fata de acest punct ales;
    // apoi incep ce iau punctele sortate si ma tot uit sa vad ce devierie se produc la introducerea fiecarui punct in infasuratoare


    //le am sortate si incep scanarea; //tin o stiva pt ca eu tot timpul trebuie sa ma uit la ultimul introdus (evident la ala dinaintea astuia pe care il bag acum)
    //bag pct initial
    a.push_back( poz );//bag pozitia in vectorul initial a punctului initial ales
    a.push_back( puncte[0] );//il bag si pe aldoilea; ca eu am nevoie de minim 3 tot timpul
    for(int i=1; i<puncte.size(); ++i){
        //cout << puncte[i] << "\n";
        //iau punctul asta si vad cate pot scoate; pp ca asta face parte din infasuratoare
        //acum scot toate punctele care sunt in interior; asta o fac cu determinant ; le scot si pe alea care sunt coliniare
        int ultim = a.size() - 1;// imi indica la ultimul punct bagat
        //cout << a[ultim-1] << " " << a[ultim] << " " << puncte[i] << "\n";
        while( a.size() >= 2 &&  semn( a[ultim-1], a[ultim], puncte[i] ) > 0.0000000 ){
            //ultimul punct il scot daca se afla in semiplanul din stanga a dreptei formate de pct-le a[ultim-1], puncte[i])
            //adica e in interior
            a.pop_back();
            --ultim;
        }
        a.push_back( puncte[i] );
    }
    g << a.size() << "\n";
    g << fixed;
    for(int i=a.size()-1; i>=0; --i){
        g << setprecision(12) << v[ a[i] ].first << " " << setprecision(12)<< v[ a[i] ].second << "\n";
    }
}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}