Cod sursa(job #3041843)

Utilizator ciacliboiiiciacli stefan ciacliboiii Data 1 aprilie 2023 22:46:13
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include<fstream>
#include<stdio.h>
#include<vector>
#include<math.h>
#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, poz, c, ind, ok, use[120005];
double unghi, u, z, x[120005], y[120005];
vector<int> ans;
int main()
{
    fin >> n;
    for(int i = 1; i <= n; ++ i)
        fin >> x[i] >> y[i];
    ind = 1;
    for(int i = 2; i <= n; ++ i)
        if(x[i] < x[ind])
            ind = i;
    c= ind;
    ok = 1;
    u = 0;
    while(ok || ind != c)
    {
        ok = 0;
        z = 100001;
        poz = c;
        ans.push_back(c);
        for(int i = 1; i <= n; ++ i)
        {
            if(use[i] || i == c)
                continue;
            unghi = atan2((x[i] - x[c]), (y[i] - y[c]));
            if(unghi < 0)
                unghi += 2 * M_PI;
            unghi -= u;
            if(unghi < 0)
                unghi += 2 * M_PI;
            if(z > unghi)
            {
                z = unghi;
                poz = i;
            }
        }
        u = atan2(-(x[c] - x[poz]), -(y[c] - y[poz]));
        if(u < 0)
            u += 2 * M_PI;
        c = poz;
        use[c] = 1;

    }
    int h = ans.size();
    fout << h << '\n';
    reverse(ans.begin(), ans.end());
    for(int i = 0; i < h; ++ i)
        fout<< fixed << setprecision(6) << x[ans[i]] << ' ' << y[ans[i]] << '\n';
    return 0;
}