Cod sursa(job #3332708)

Utilizator tudorvoieVoie Tudor tudorvoie Data 8 ianuarie 2026 17:55:59
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, verif[120001];
double x[120001], y[120001];
vector<int> v;

int main() {
    ios::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);
    fin >> n;
    x[0] = 1000000000; y[0] = 1000000000;
    int initial = 0;
    for (int i = 1; i <= n; i++)
    {
        fin >> x[i] >> y[i];
        if (x[i] < x[initial]) initial = i;
    }
    int acuma = initial;
    double inainte = 0;
    do
    {
        v.push_back(acuma);
        double maxim = DBL_MAX;
        int nou = acuma;
        for (int i = 1; i <= n; i++)
        {
            if (acuma != i && !verif[i])
            {
                double unghi = atan2((x[i] - x[acuma]), (y[i] - y[acuma]));
                if (unghi < 0) unghi += 2 * M_PI;
                unghi = unghi - inainte;
                if (unghi < 0) unghi += 2 * M_PI;
                if (unghi < maxim)
                {
                    maxim = unghi;
                    nou = i;
                }
            }
        }
        inainte = atan2(x[nou] - x[acuma], y[nou] - y[acuma]);
        if (inainte < 0) inainte += 2 * M_PI;
        acuma = nou;
        verif[nou] = 1;
    } while (initial != acuma);
    reverse(v.begin(), v.end());
    fout << v.size() << '\n';
    fout << setprecision(12) << fixed;
    for (auto i : v)
    {
        fout << x[i] << " " << y[i] << '\n';
    }
    return 0;
}