Cod sursa(job #916477)

Utilizator mihai995mihai995 mihai995 Data 16 martie 2013 16:06:21
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <stack>
#include <iomanip>
using namespace std;

const int N = 120005;
const double E = 1e-12;

struct Point{
    double x, y;

    Point(){
        x = y = 0;
    }

    Point(double _x, double _y){
        x = _x;
        y = _y;
    }

    inline Point operator-(Point P){
        return Point(x - P.x, y - P.y);
    }

    inline bool operator<(const Point& P) const {
        return x < P.x || (x == P.x && y < P.y);
    }
};

class ConvexHull{
    inline bool bad(Point A, Point B){
        return A.x * B.y - A.y * B.x < E;
    }

    inline bool bad(Point A, Point B, Point C){
        return bad(B - A, C - A);
    }

    void compute(vector<Point>& v, vector<int>& index, bool use[], int x, int lim){
        while (index.size() > lim && bad( v[ index[ index.size() - 2 ] ], v[ index.back() ], v[x] )){
            use[index.back()] = false;
            index.pop_back();
        }

        if (use[x])
            return;

        index.push_back(x);
        use[x] = true;
    }

public:
    void convexHull(vector<Point>& v){
        vector<int> index;
        bool use[v.size()];

        sort(v.begin(), v.end());
        memset(use, false, sizeof(use));

        int lim = 1;

        for (int i = 0 ; i < v.size() ; i++)
            compute(v, index, use, i, lim);

        lim = index.size();

        for (int i = v.size() - 1 ; i >= 0 ; i--)
            compute(v, index, use, i, lim);

        vector<Point> ans;
        ans.reserve(index.size());

        for (vector<int> :: iterator it = index.begin() ; it != index.end() ; it++)
            ans.push_back(v[*it]);

        v.swap(ans);
    }
};

ConvexHull H;
vector<Point> v;

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

int main(){
    int n;
    double x, y;

    in >> n;

    v.reserve(n);

    while(n--){
        in >> x >> y;

        v.push_back(Point(x, y));
    }

    H.convexHull(v);

    out << v.size() << "\n";

    out << setprecision(6) << fixed;

    for (vector<Point> :: iterator it = v.begin() ; it != v.end() ; it++)
        out << (it -> x) << " " << (it -> y) << "\n";

    return 0;
}