Cod sursa(job #2722668)

Utilizator BAlexandruBorgovan Alexandru BAlexandru Data 13 martie 2021 10:20:15
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

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

struct point
{
    double x, y;

    point()
    {
        x = 0;
        y = 0;
    }

    point(double X, double Y)
    {
        x = X;
        y = Y;
    }
};

const double PI = atan(1) * 4;

int n;

bool used[120001];

point p[120001];

int main()
{
    f >> n;

    for (int i=1; i<=n; i++)
        f >> p[i].x >> p[i].y;

    int first = 1;
    for (int i=1; i<=n; i++)
        if (p[i].x < p[first].x)
            first = i;

    bool m = true;
    int cur = first;
    double last = 0;

    vector < int > ans;

    while (m || cur != first)
    {
        m = false;

        ans.push_back(cur);

        double ma = 10000;
        int pos = 0;

        for (int i=1; i<=n; i++)
            if (!used[i] && i != cur)
            {
                double unghi = atan2(p[i].x - p[cur].x, p[i].y - p[cur].y);

                if (unghi < 0)
                    unghi += 2.0 * PI;

                unghi -= last;

                if (unghi < 0)
                    unghi += 2.0 * PI;

                if (unghi < ma)
                {
                    ma = unghi;
                    pos = i;
                }
            }

        last = atan2(p[pos].x - p[cur].x, p[pos].y - p[cur].y);

        if (last < 0)
            last += 2 * PI;

        cur = pos;
        used[cur] = true;
    }

    g << ans.size() << "\n";
    for (int i=ans.size()-1; i>=0; i--)
        g << fixed << setprecision(6) << p[ans[i]].x << " " << p[ans[i]].y << "\n";

    return 0;
}