Cod sursa(job #2417634)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 30 aprilie 2019 17:01:41
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.22 kb
#include <bits/stdc++.h>

#define ldb long double
#define point_data std::pair <ldb, ldb>

std::istream& operator >> (std::istream& stream, point_data& data) {
    return stream >> data.first >> data.second;
}
std::ostream& operator << (std::ostream& stream, point_data data) {
    return stream << data.first << ' ' << data.second;
}

#define EPS (1e-10)
#define x   first
#define y  second

point_data origin;
double crossProduct(const point_data& A, const point_data& B, const point_data& C) {
    return (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
}

class ConvexHull {
protected:
    std::vector <point_data> *pointsArrPtr;
    std::vector <int> hullPoints;

public:
    ConvexHull(std::vector <point_data>& points) {
        pointsArrPtr = &points;
        int hullBegin = 0;
        for (int i=1; i<points.size(); ++i)
            if (points[i] < points[hullBegin])
                hullBegin = i;
        std::swap(points[0], points[hullBegin]);
        origin = points[0];
        std::sort(points.begin()+1, points.end(), [](const point_data& p0, const point_data& p1)->bool {
                  return crossProduct(origin, p0, p1) < EPS;});

        hullPoints.push_back(0);
        hullPoints.push_back(1);
        for (int i=2; i<points.size(); ++i) {
            while (hullPoints.size()>1 && crossProduct(points[hullPoints[hullPoints.size()-2]], points[hullPoints.back()], points[i]) > EPS)
                   hullPoints.pop_back();
            hullPoints.push_back(i);
        }
    }

    int size() {return hullPoints.size();}
    point_data point(int idx) {return (*pointsArrPtr)[hullPoints[idx]];}
    int operator [] (int idx) {return hullPoints[idx];}
};

int N;
std::vector <point_data> V;

std::ifstream input ("infasuratoare.in");
std::ofstream output("infasuratoare.out");

void readInput() {
    input >> N;
    V.resize(N);
    for (auto &it:V)
        input >> it;
}

void solveInput() {
    ConvexHull hull(V);
    output << hull.size() << '\n';
    output << std::fixed << std::setprecision(6);
    for (int i=0; i<hull.size(); ++i)
        output << hull.point(hull.size()-i-1) << '\n';
}

int main()
{
    readInput();
    solveInput();

    return 0;
}