Cod sursa(job #2412662)

Utilizator petrisorvmyVamanu Petru Gabriel petrisorvmy Data 22 aprilie 2019 14:25:47
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <algorithm>
#define ld long double
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
pair<ld,ld> v[120001];
bool viz[120001];
vector<int> ans;
int main()
{
    ld PI = 2*asin(1);
    f >> n;
    for(int i = 1; i <= n; ++i)
        f >> v[i].x >> v[i].y;
    int poz = 0, act = 0, ok = 1;
    v[0].x = v[0].y = 1000000000;
    for(int i = 1; i <= n; ++i)
        if(v[i].x < v[poz]. x) poz = i;
    act = poz;
    ld last = 0;
    while(ok || act != poz)
    {
        ok = 0;
        ans.push_back(act);
        int neww = act;
        ld ma = 10000;
        for(int i = 1; i <= n; ++i)
        {
            if(viz[i] || i == act) continue;
            ld unghi = atan2( (v[i].x - v[act].x), v[i].y-v[act].y);
            if(unghi < 0) unghi += 2* PI;
            unghi -= last;
            if(unghi < 0) unghi += 2* PI;
            if(ma > unghi)
            {
                ma = unghi;
                neww = i;
            }
        }
        last = atan2( v[neww].x- v[act].x, v[neww].y - v[act].y );
        if(last < 0) last += 2* PI;
        act = neww;
        viz[act] = 1;
    }
    reverse(ans.begin(), ans.end());
    g << ans.size() << '\n' << setprecision(6) << fixed;
    for(int i = 0; i < ans.size(); ++i)
        g << v[ans[i] ].x << ' ' << v[ans[i]].y << '\n';
    f.close();
    g.close();
    return 0;
}