Cod sursa(job #3332710)

Utilizator tudorvoieVoie Tudor tudorvoie Data 8 ianuarie 2026 18:02:49
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 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);
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d\n",&n);
    x[0] = 1000000000; y[0] = 1000000000;
    int initial = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lf %lf\n",&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;
    printf("%d\n",v.size());
    for (auto i : v)
    {
        printf("%lf %lf\n",x[i],y[i]);
    }
    return 0;
}