Cod sursa(job #2499075)

Utilizator rd211Dinucu David rd211 Data 25 noiembrie 2019 11:22:05
Problema Adapost 2 Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
const int NMAX = 50010;
int n;
pair<double,double> Points[NMAX];
double calcDist(pair<double,double> newPoint)
{
    double distance=0.0;
    for(int i = 0;i<n;i++)
    {
        distance+= sqrt((Points[i].first-newPoint.first)*(Points[i].first-newPoint.first)+
                   (Points[i].second-newPoint.second)*(Points[i].second-newPoint.second));
    }
    return distance;
}
int main()
{
    fin>>n;
    for(int i = 0;i<n;i++)
    {
        double x,y;
        fin>>x>>y;
        Points[i]={x,y};
    }
    double multi = 500.0;
    pair<double,double> currentPoint;
    while(multi>0.000001)
    {
        pair<double,double> topPoint = {currentPoint.first,currentPoint.second+multi},
                            bottomPoint = {currentPoint.first,currentPoint.second-multi},
                            leftPoint = {currentPoint.first-multi,currentPoint.second},
                            rightPoint = {currentPoint.first+multi,currentPoint.second};

        double topDistance = calcDist(topPoint),
                bottomDistance = calcDist(bottomPoint),
                leftDistance = calcDist(leftPoint),
                rightDistance = calcDist(rightPoint),
                currentDistance = calcDist(currentPoint);

        if(topDistance<=bottomDistance && topDistance<=leftDistance && topDistance<=rightDistance && topDistance<=currentDistance)
        {
            currentPoint = topPoint;
        }
        else if(bottomDistance<=topDistance && bottomDistance<=leftDistance && bottomDistance<=rightDistance && bottomDistance<=currentDistance)
        {
            currentPoint = bottomPoint;

        }
        else if(leftDistance<=bottomDistance && leftDistance<=topDistance && leftDistance<=rightDistance && leftDistance<=currentDistance)
        {
            currentPoint = leftPoint;

        }
        else if(rightDistance<=bottomDistance && rightDistance<=leftDistance && rightDistance<=topDistance && rightDistance<=currentDistance)
        {
            currentPoint = rightPoint;
        }
        else
        {
            multi/=2;
        }
    }
    fout<<fixed<<setprecision(4)<<currentPoint.first<<" "<<currentPoint.second;
    return 0;
}