Cod sursa(job #701886)

Utilizator vendettaSalajan Razvan vendetta Data 1 martie 2012 18:20:42
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
#define nmax 120005

using namespace std;

int n;
vector<pair<double, double> > pct, st;


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

bool cmp(pair<double,double> a, pair<double,double> b){

    if ( (a.x < b.x) || (a.x == b.x && a.y < b.y) )
        return true;
    else return false;

}

void citeste(){

    f >> n;

    //citesc punctele
    for(int i=1; i<=n; i++){
        double x, y;
        f >> x >> y;
        pct.push_back(make_pair(x,y));
    }

    //le sortez crescator dupa x si in caz de egalitate dupa y
    sort(pct.begin(), pct.end(), cmp );

}

bool verif(pair<double,double> A, pair<double,double> B, pair<double,double> C){

    double a = A.y - B.y;//y1 - y2
    double b = B.x - A.x;//x2 - x1
    double c = A.x*B.y - B.x * A.y;//x1 * y2 - x2 * y1;

    double ecu = a * C.x + b * C.y + c;

    return (ecu < 0);

}

void rezolva(){

    //adaug primele 2 pct
    st.push_back(make_pair(pct[0].x, pct[0].y));
    st.push_back(make_pair(pct[1].x, pct[1].y));

    for(int i=2; i<pct.size(); i++){
        while (st.size() > 1 && verif( st[st.size()-2], st[st.size()-1], pct[i] ) )
            st.pop_back();
        st.push_back(make_pair(pct[i].x, pct[i].y));
    }

    for(int i=pct.size()-2; i>=0; i--){
        while (st.size() > 1 && verif( st[st.size()-2], st[st.size()-1], pct[i] ) )
            st.pop_back();
        st.push_back(make_pair(pct[i].x, pct[i].y));
    }

    st.pop_back();

}

void scrie(){

    g << st.size() << "\n";

    for(int i=0; i<st.size(); i++){
        g << fixed;
        g << setprecision(12) << st[i].x << " " << setprecision(12) << st[i].y << "\n";
    }


}

int main(){

    citeste();
    rezolva();
    scrie();

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

    return 0;


}