Cod sursa(job #2571173)

Utilizator AndreibatmanAndrei Croitoriu Andreibatman Data 4 martie 2020 21:24:55
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb

#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct ceva
{
    double x,y;
    bool viz;
}v[120010],sol[120010];
int n,i,poz,nr,pozinit;
int dist(ceva a,ceva b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int ok(int i,int poz,int poz2)
{
    return (i!=poz && i!=poz2 && v[i].viz==0);
}
double get_unghi(ceva a,ceva b,ceva c)
{
    double ab,ac,bc;
    ab=dist(a,b);
    bc=dist(b,c);
    ac=dist(a,c);
    return (acos((ab*ab+bc*bc-ac*ac)/(2*ab*bc)))*180/3.1415;
}
void get_infasuratoare(ceva a,ceva b,int poz,int poz2)
{
    if(poz2==pozinit)
        return;
    int pozitie=0;
    double unghimax=-10000,unghi=0,altok=0;
    for(i=1;i<=n;i++)
    {
        altok=1;
        unghi=get_unghi(a,b,v[i]);
        if(unghi>=unghimax)
            unghimax=unghi , pozitie=i;
    }
    if(v[pozitie].viz==1)
        return;
    sol[++nr].x=v[pozitie].x;
    sol[nr].y=v[pozitie].y;
    v[pozitie].viz=true;
    get_infasuratoare(b,v[pozitie],poz,pozitie);
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>v[i].x>>v[i].y;
        if(v[i].x<v[poz].x || poz==0)
            poz=i;
        else if(v[i].x==v[poz].x && v[i].y<v[poz].y)
            poz=i;
    }
    v[poz].viz=1;
    sol[++nr].x=v[poz].x;
    sol[nr].y=v[poz].y;
    pozinit=poz;
    get_infasuratoare({v[poz].x+10,v[poz].y,0},v[poz],poz,0);
    fout<<nr<<'\n';
    for(i=nr;i>=1;i--)
        fout<<fixed<<setprecision(6)<<sol[i].x<<" "<<sol[i].y<<'\n';
    return 0;
}