Cod sursa(job #3332716)

Utilizator tudorvoieVoie Tudor tudorvoie Data 8 ianuarie 2026 18:20:21
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.72 kb
#include <bits/stdc++.h>
using namespace std;

#define DIM 10000
char buff[DIM];
int poz=0;


void citeste(double &numar)
{
    numar = 0;
    char semn='+';
    //caut inceputul numarului
    while (buff[poz] < '0' || buff[poz] > '9')
    {
        semn = buff[poz];
        if (++poz == DIM)
            fread(buff,1,DIM,stdin),poz=0;
    }
    //citesc partea de dinainte de virgula
    while ('0'<=buff[poz] && buff[poz]<='9')
    {
        numar = numar*10 + buff[poz] - '0';
        if (++poz == DIM)
            fread(buff,1,DIM,stdin),poz=0;
    }
    //daca are virgula citesc si partea de dupa
    if (buff[poz] == '.')
    {
        double tmp,cnt;
        tmp = 0;
        cnt = 1;
        ++poz;
        while ('0'<=buff[poz] && buff[poz]<='9')
        {
            cnt = cnt/10;
            tmp = tmp + cnt*(double(buff[poz]-'0'));
            if (++poz == DIM)
                fread(buff,1,DIM,stdin),poz=0;
        }
        numar += tmp;
    }
    //daca are semnul minus il fac negativ
    if (semn == '-')
        numar = - numar;
}

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



int main() {
    int n, verif[120001] = {0};
    double x[120001], y[120001];
    vector<int> v;
    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);
    fin >> n;
    x[0] = 1000000000; y[0] = 1000000000;
    int initial = 0;
    for (int i = 1; i <= n; i++)
    {
        //fin >> x[i];
        //fin>> y[i];
        citeste(x[i]);
        citeste(y[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]);
        fout << x[i] << " " << y[i] << '\n';
    }
    return 0;
}