Cod sursa(job #3203563)

Utilizator DomnulMilandruMilandru Nicon-David DomnulMilandru Data 13 februarie 2024 21:41:53
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb

#include <fstream>
#include <vector>
#include <cmath>
#include<math.h>
#include<stdio.h>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n;
vector<double> X,Y;
int punct_initial,curent;
int movey;
vector<int> ans;
vector<bool> fr;
int main()
{
    cout<<setprecision(6)<<fixed;
    cin>>n;
    X.resize(n+1);
    Y.resize(n+1);
    fr.resize(n+1);
    X[0]=1000000000;
    Y[0]=1000000000;
    for(int i=1;i<=n;i++)
      cin>>X[i]>>Y[i];
    for(int i=1;i<=n;i++)
      if(X[i]<X[punct_initial])
         punct_initial=i;
    curent=punct_initial;
    double last=0;
    for(int i=1;i<=6;i++)
    while(!movey || curent!=punct_initial)
    {
        movey=1;
        ans.push_back(curent);
        int poz=0;
        double mini=1000000;
        for(int i=1;i<=n;i++)
          {
              if(fr[i] || curent==i)
                continue;
              double unghi=atan2(X[i]-X[curent],Y[i]-Y[curent]);
              if(unghi<0)
                unghi=unghi+2*M_PI;
            unghi=unghi-last;
             if(unghi<0)
               unghi=unghi+2*M_PI;
            if(unghi<mini)
             {
                 mini=unghi;
                 poz=i;
             }
          }
        last=atan2((X[poz]-X[curent]),(Y[poz]-Y[curent]));
        if(last<0)
           last=last+2*M_PI;
        curent=poz;
        fr[curent]=1;
    }
    cout<<ans.size()<<'\n';
    for(int i=ans.size()-1;i>=0;i--)
      cout<<X[ans[i]]<<" "<<Y[ans[i]]<<'\n';
    return 0;
}