Cod sursa(job #2974580)

Utilizator rusu_mateiRusu Matei rusu_matei Data 4 februarie 2023 11:20:23
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include<fstream>
#include<cmath>
#include<vector>
#include<iomanip>
#include<algorithm>
#define dim 120005
using namespace std;
ifstream in("infasuratoareconvexa.in");
ofstream out("infasuratoareconvexa.out");
vector<int>v;
double x[dim],y[dim];
bool use[dim],ok;
int n,h;
void citire()
{
    in>>n;
    for(int i=1; i<=n; i++)
        in>>x[i]>>y[i];
}
int main()
{
    citire();
    int mic=1,c,poz;
    double unghi,minU,uAnt;
    for(int i=2; i<=n; i++)
        if(x[i]<x[mic])
            mic=i;
    c=mic;
    ok=1;
    uAnt=0;
    while(ok==1 || c!=mic)
    {
        ok=0;
        v.push_back(c);
        poz=c;
        minU=10000;
        for(int i=1; i<=n; i++)
        {
            if(use[i]==1 || i==c)
                continue;
            unghi=atan2((x[i]-x[c]),(y[i]-y[c]));
            if(unghi<0)
                unghi+=2*M_PI;
            unghi-=uAnt;

            if(unghi<0)
                unghi+=2*M_PI;
            if(minU>unghi)
            {
                minU=unghi;
                poz=i;
            }
        }
        uAnt=atan2(-(x[c]-x[poz]),-(y[c]-y[poz]));
        if(uAnt<0)
            uAnt+=2*M_PI;
        c=poz;
        use[c]=1;
    }
    reverse(v.begin(),v.end());
    h=v.size();
    out<<h<<"\n";
    for(int i=0; i<h; i++)
        out<<fixed<<setprecision(6)<<x[v[i]]<<" "<<y[v[i]]<<"\n";
    return 0;
}