Cod sursa(job #3205521)

Utilizator DomnulMilandruMilandru Nicon-David DomnulMilandru Data 19 februarie 2024 21:33:41
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.1 kb
#include <fstream>
#include <vector>
#include <cmath>
#include<math.h>
#include<stdio.h>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("mosia.in");
ofstream cout("mosia.out");
int n;
vector<double> X,Y;
int punct_initial,curent;
int movey;
vector<int> ans;
vector<bool> fr;
vector<double> D;
vector<double> A;
double distanta(int i,int j)
{
    double nr1=X[i]-X[j];
    nr1=nr1*nr1;
    double nr2=Y[i]-Y[j];
    nr2=nr2*nr2;
    return sqrt(nr1+nr2);
}
double Arie(int i,int j,int k)
{
    double arie=D[j]*distanta(i,k);
    return arie/2;
}
int main()
{
    cout<<setprecision(6)<<fixed;
    cin>>n;
    X.resize(n+1);
    Y.resize(n+1);
    fr.resize(n+1);
    D.resize(n+1);
    X[0]=1000000000;
    Y[0]=1000000000;
    for(int i=1;i<=n;i++)
      cin>>X[i]>>Y[i]>>D[i];
    for(int i=1;i<=n;i++)
      if(X[i]<X[punct_initial])
         punct_initial=i;
    curent=punct_initial;
    double last=0;
    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;
    }
    A.resize(n+1);
    A[0]=Arie(ans[ans.size()-1],ans[0],ans[1]);
    for(int i=1;i<ans.size()-1;i++)
          A[i]=Arie(ans[i-1],ans[i],ans[i+1]);
    A[ans.size()-1]=Arie(ans.size()-2,ans.size()-1,ans[0]);
    double a=0;
    double b=0;
    for(int i=0;i<ans.size();i++)
       if(i%2==0)
         a=a+A[i];
       else
        b=b+A[i];
    cout<<max(a,b);
    return 0;
}