Cod sursa(job #2569702)

Utilizator AndreibatmanAndrei Croitoriu Andreibatman Data 4 martie 2020 13:15:34
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 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 crossproduct(ceva a,ceva b)
{
    return a.x*b.y-a.y*b.x;
}
int ok(int i,int poz,int poz2)
{
    return (i!=poz && i!=poz2 && v[i].viz==0);
}
int get_unghi(ceva a,ceva b,ceva c)
{
    double ab,ac,bc;
    ab=crossproduct(a,b);
    bc=crossproduct(b,c);
    ac=crossproduct(a,c);
    return (ab*ab+ac*ac-bc*bc)/(2*ab*ac);
}
void get_infasuratoare(ceva a,ceva b,int poz,int poz2)
{
    if(poz2==pozinit)
        return;
    int pozitie=0,unghimax=-10000,unghi=0,altok=0;
    for(i=1;i<=n;i++)
        if(ok(i,poz,poz2))
        {
            altok=1;
            unghi=abs(get_unghi(a,b,v[i]));
            if(unghi>unghimax)
                unghimax=unghi , pozitie=i;
        }
    if(altok==0)
        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].y<v[poz].x || poz==0)
            poz=i;
        else if(v[i].y==v[poz].y && v[i].x<v[poz].x)
            poz=i;
    }
    sol[++nr].x=v[poz].x;
    sol[nr].y=v[poz].y;
    pozinit=poz;
    get_infasuratoare(v[poz],{v[poz].x,v[poz].y+10,0},poz,0);
    fout<<nr<<'\n';
    for(i=1;i<=nr;i++)
        fout<<fixed<<setprecision(6)<<sol[i].x<<" "<<sol[i].y<<'\n';
    return 0;
}