Cod sursa(job #1117497)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 23 februarie 2014 16:37:56
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.78 kb
/// POO concepts
#include <fstream>
#include <iostream>
#include <vector>
#include <bitset>
#include <string.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <stack>

using namespace std;

const char infile[] = "infasuratoare.in";
const char outfile[] = "infasuratoare.out";

ifstream fin(infile);
ofstream fout(outfile);

const int MAXN = 100005;
const double oo = 0x3f3f3f3f;

typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;

const inline int min(const int &a, const int &b) { if( a > b ) return b;   return a; }
const inline int max(const int &a, const int &b) { if( a < b ) return b;   return a; }
const inline void Get_min(int &a, const int b)    { if( a > b ) a = b; }
const inline void Get_max(int &a, const int b)    { if( a < b ) a = b; }

#define x first
#define y second

#define T double

vector<pair<T, T> > Points;
pair<T, T> _Origin = make_pair(oo, oo);
int N, M;
int lowInd;

inline double crossPoint(const pair<T, T> &A, const pair<T, T> &B, const pair<T, T> &C) {
    return (B.x - A.x) * (C.y - A.y)  - (B.y - A.y) * (C.x - A.x);
}

struct classComp {
    inline bool operator () (const pair<T, T> &a, const pair<T, T> &b) const {
        return crossPoint(_Origin, a, b) < 0;
    }
};

inline void addPoint(pair<T, T> P) {
    if(_Origin > P) {
        _Origin = P;
        lowInd = M;
    }
    Points.push_back(P);
    ++ M;
}

inline void sortPoint() {
    swap(Points[0], Points[lowInd]);
    sort(Points.begin() + 1, Points.end(), classComp());
}

inline stack < pair<T, T> > ConvexHull() {
    stack < pair<T, T> > st;
    vector < pair<T, T> > :: iterator it = Points.begin();
    st.push(*it);
    ++ it;
    st.push(*it);
    for(++ it ; it != Points.end() ; ++ it) {
        while(st.size() > 1) {
            pair<T, T> p1 = st.top();
            st.pop();
            pair<T, T> p2 = st.top();
            st.pop();
            if(crossPoint(p2, p1, *it) > 0)
                st.push(p2);
            else {
                st.push(p2);
                st.push(p1);
                break;
            }
        }
        st.push(*it);
    }
    return st;
}

int main() {
    fin >> N;
    for(int i = 1 ; i <= N ; ++ i) {
        pair<double, double> X;
        fin >> X.x >> X.y;
        addPoint(X);
    }
    sortPoint();
    stack <pair<double, double > > convexHull = ConvexHull();
    fout << convexHull.size() << fixed << setprecision(6) << '\n';
    while(!convexHull.empty()) {
        fout << convexHull.top().first << ' ' << convexHull.top().second << '\n';
        convexHull.pop();
    }
    fin.close();
    fout.close();
    return 0;
}