Cod sursa(job #1089163)

Utilizator RobertSSamoilescu Robert RobertS Data 21 ianuarie 2014 15:55:35
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.5 kb
#include<iostream>
#include<fstream>
#include<vector>
#include <iomanip>
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

const int MAX_N = 120001;

int n;
double x[MAX_N], y[MAX_N];
double min_x, min_y;

void read(){
    fin >> n;

    fin >> x[1] >>  y[1];

    min_x  = x[1];
    min_y = y[1];

    for(int i=2; i<=n; i++){
        fin >> x[i] >> y[i];

        if(x[i] < min_x){
            min_x =  x[i];
            min_y = y[i];
        }else if(x[i] == min_x){
            if(y[i] < min_y){
                min_y = y[i];
            }
        }
    }


}

struct Point{
    double x, y;
    double tg;
};

vector<Point> list;// lista in care ordonez punctele in functie de tangenta cu punctul de coordonate (min_X, min_y)


#define pb push_back

void addToList(Point p, int li, int ls){
    if(list.size() == 0){
        list.pb(p);
    }else if(ls - li == 0){
        int lm = (li+ls)/2;
        if(list[lm].tg > p.tg){
            list.insert(list.begin() + lm , p);
        }else list.insert(list.begin()+lm+1, p);
    }else {
        int lm = (li+ls)/2;
        if(list[lm].tg < p.tg) addToList(p, lm+1, ls);
        else addToList(p, li, lm);
    }

}

void sort(){
    for(int i=1; i<=n; i++){
        if(x[i] != min_x || y[i] != min_y){
            Point p;
            p.x = x[i];
            p.y = y[i];
            p.tg = (p.y - min_y)/(p.x - min_x);
            addToList(p,0, list.size()-1);
        }
    }

}

vector<Point> st;

void solve(){
    Point p;
    p.x = min_x;
    p.y = min_y;

    st.push_back(p);
    st.push_back(list[0]);

    // (x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)
    for(size_t i=1; i<list.size(); i++){
        size_t lung = st.size()-1;
        double x1 = st[lung-1].x;
        double y1 = st[lung-1].y;
        double x2 = st[lung].x;
        double y2 = st[lung].y;
        double x3 = list[i].x;
        double y3 = list[i].y;

        double res = (x2-x1)*(y3-y1)-(y2-y1)*(x3-x1);
        if(res > 0) st.push_back(list[i]);
        else{
            st.pop_back();
            st.push_back(list[i]);
        }


    }
    fout << st.size() << '\n';
    fout.setf( std::ios::fixed, std:: ios::floatfield );
    fout.precision(20);
    for(size_t i=1; i<st.size(); i++){
        fout << st[i].x <<  " " << st[i].y << '\n';
    }
    fout << st[0].x << " " << st[0].y << '\n';

}

int main(){

    read();
    sort();
    solve();

return 0;
}