Cod sursa(job #916422)

Utilizator mihai995mihai995 mihai995 Data 16 martie 2013 14:43:02
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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 <= 0;
    }

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

public:
    void convexHull(vector<Point>& v){
        vector<Point> ans;

        sort(v.begin(), v.end());

        for (size_t i = 0 ; i < v.size() ; i++){
            while (ans.size() > 1 && bad(ans[ ans.size() - 2 ], ans.back(), v[i]))
                ans.pop_back();

            ans.push_back(v[i]);
        }

        int sMin = ans.size();

        for (size_t i = v.size() - 2 ; i ; i--){
            while (ans.size() > sMin && bad(ans[ ans.size() - 2 ], ans.back(), v[i]))
                ans.pop_back();

            ans.push_back(v[i]);
        }

        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";

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

    return 0;
}