Cod sursa(job #1966569)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 15 aprilie 2017 13:09:26
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
struct
{
    double x,y;
}v[120003];
int n,m,ap[120003],sol[120003],st,ok=1,act;
int main()
{
    f>>n;
    v[0].x=v[0].y=1000000000;
    for(int i=1;i<=n;++i) f>>v[i].x>>v[i].y;
    for(int i=1;i<=n;++i) if(v[i].x<v[st].x) st=i;
    act=st;
    double last=0;
    while(ok||st!=act)
    {
        ok=0;
        sol[++m]=act;
        double ma=10000;
        int poznoua=act;
        for(int i=1;i<=n;++i)
        {
            if(ap[i]||i==act) continue;
            double unghi=atan2((v[i].x-v[act].x),v[i].y-v[act].y);
            if(unghi<0) unghi+=2*M_PI;
            unghi-=last;
            if(unghi<0) unghi+=2*M_PI;
            if(ma>unghi) {ma=unghi;poznoua=i;}
        }
        last=atan2((v[poznoua].x-v[act].x),v[poznoua].y-v[act].y);
        if(last<0) last+=2*M_PI;
        act=poznoua;
        ap[act]=1;
    }
    g<<m<<'\n';
    for(int i=m;i>=1;--i) g<<fixed<<setprecision(6)<<v[sol[i]].x<<' '<<fixed<<setprecision(6)<<v[sol[i]].y<<'\n';
    return 0;
}