Cod sursa(job #2890785)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 16 aprilie 2022 16:35:04
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.62 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

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

// ^
// |
// |y
// ------> x
const double EPS = 1e-12;


struct Dot
{
    double x;
    double y;

    inline Dot operator- (const Dot& a) const
    {
        Dot result;
        result.x = x - a.x;
        result.y = y - a.y;
        return result;
    }
};

inline bool LessThan(const double& a, const double& b) {
    return (a - b < -EPS);
}

inline bool GreaterThan(const double& a, const double& b) {
    return (a - b > EPS);
}

inline bool Equals(const double a, const double b) {
    return (a - b < EPS && a - b > -EPS);
}


int n;
vector <Dot> dots;
vector <Dot> convexHull;

double CrossProduct(const Dot& a, const Dot& b)
{
    return (a.x * b.y) - (a.y * b.x);
}

bool cmp(const Dot& a, const Dot& b) {
    return LessThan(CrossProduct(a - dots[0], b - dots[0]), 0);
}

int GetPivotPoint() {
    Dot bestPivot = {0x3f3f3f3f, 0x3f3f3f3f};
    int index = -1;
    for (int i = 0; i < n; i++)
    {
        if (LessThan(dots[i].x, bestPivot.x) || 
            (Equals(dots[i].x, bestPivot.x) && LessThan(dots[i].y, bestPivot.y))) {
            bestPivot = dots[i];
            index = i;
        }
    }
    return index;
}

void GenerateConvexHull()
{
    convexHull.push_back(dots[0]);
    convexHull.push_back(dots[1]);

    for (int currIdx = 2; currIdx < n; currIdx++)
    {
        Dot lastVec = convexHull[convexHull.size() - 2] - convexHull[convexHull.size() - 1];
        Dot currDot = dots[currIdx];
        Dot currVec = convexHull[convexHull.size() - 2] - currDot;

        while (GreaterThan(CrossProduct(lastVec, currVec), 0))
        {
            convexHull.pop_back();

            lastVec = convexHull[convexHull.size() - 2] - convexHull[convexHull.size() - 1];
            currDot = dots[currIdx];
            currVec = convexHull[convexHull.size() - 2] - currDot;
        }

        convexHull.push_back(currDot);
    }
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        double x, y;
        fin >> x >> y;
        dots.push_back({x, y});
    }

    int pivotIdx = GetPivotPoint();
    swap(dots[0], dots[pivotIdx]);
    sort(dots.begin() + 1, dots.end(), cmp);
    
    GenerateConvexHull();

    fout << convexHull.size() << '\n';
    fout << fixed << setprecision(12);
    std::for_each(convexHull.rbegin(), convexHull.rend(), [](const Dot& currDot){
        fout << currDot.x << ' ' << currDot.y << '\n';
    });

}