Cod sursa(job #3122861)

Utilizator code_blocksSpiridon Mihnea-Andrei code_blocks Data 20 aprilie 2023 20:58:29
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.51 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

typedef unsigned int uint;

const string task = "infasuratoare";

class Point
{
public:
    double x;
    double y;

    Point(double _x = 0, double _y = 0)
    {
        this->x = _x;
        this->y = _y;
    }
};

namespace utils
{
    char orientation(Point a, Point b, Point c)
    {
        double delta = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);

        if(delta == 0)
        {
            return '*';
        }
        else if(delta > 0)
        {
            return '+';
        }
        else
        {
            return '-';
        }
    }

    uint begin(deque<Point> point_set)
    {
        uint best_index = 0, size = point_set.size();

        for(int index = 1; index < size; index++)
        {
            if(point_set[index].x < point_set[best_index].x)
            {
                best_index = index;
            }
        }

        return best_index;
    }
}

deque<Point> hull(deque<Point> point_set)
{
    deque<Point> Hull = {};

    uint size = point_set.size();

    if(size != 0 && size != 1 && size != 2)
    {
        uint begin_index = utils::begin(point_set), current_index = begin_index;

        do
        {
            Hull.push_back(point_set[current_index]);
            
            uint best_index = (current_index + 1) % size;

            for(uint index = 0; index < size; index++)
            {
                if(utils::orientation(point_set[current_index], point_set[index], point_set[best_index]) == '-')
                {
                    best_index = index;
                }
            }

            current_index = best_index;
        } 
        while(current_index != begin_index);
    }

    return Hull;
}

int main()
{
    uint size;

    double x, y;

    deque<Point> point_set, Hull;

    ifstream fin(task + ".in");
    ofstream fout(task + ".out");

    fin >> size;

    while(fin >> x >> y)
    {
        point_set.push_back(Point(x, y));
    }

    Hull = hull(point_set);

    sort(Hull.begin(), Hull.end(), 
    
    [] (const Point& a, const Point& b) -> bool 
    {
        return atan2(a.y, a.x) < atan2(b.y, b.x);
    }
    
    );

    fout << Hull.size() << '\n';

    for(auto point : Hull)
    {
        fout << setprecision(12) << point.x << ' ' << point.y << '\n';
    }

    return 0;
}