Cod sursa(job #2061606)

Utilizator Andreiii500Andrei Puiu Andreiii500 Data 9 noiembrie 2017 15:41:15
Problema Adapost 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<cmath> /// sqrt()
using namespace std;

ifstream in("adapost2.in");
ofstream out("adapost2.out");

const int N = 50000;
pair<double, double> v[N]; /// (x, y)
pair<double, double> x;
int n;

double distTwoPoints(pair<double, double> a, pair<double, double> b){
    return sqrt( (a.first - b.first)*(a.first - b.first) + (a.second - b.second)*(a.second - b.second) );
}

double globalDistance(pair<double, double> point){
    double distance = 0;
    for(int i=0; i<n; ++i)
        distance += distTwoPoints(point, v[i]);
    return distance;
}

int main()
{
    in>>n;
    for(int i=0; i<n; ++i)
        in>>v[i].first>>v[i].second;

    //cout<<n<<"\n"; for(int i=0; i<n; ++i) cout<<v[i].first<<" "<<v[i].second<<"\n";

    double pointJumpDistance = 512;
    pair<double, double> presumedSolution(512, 512);
    while(pointJumpDistance > 0.0002){
        ///cout<<pointJumpDistance<<"\n";
        while(1){ /// Loop until a better solution cannot be found anymore
            /// Initialize Jump points
            pair<double, double> presumedSolution_Up(presumedSolution.first, presumedSolution.second - pointJumpDistance);
            pair<double, double> presumedSolution_Down(presumedSolution.first, presumedSolution.second + pointJumpDistance);
            pair<double, double> presumedSolution_Right(presumedSolution.first + pointJumpDistance, presumedSolution.second);
            pair<double, double> presumedSolution_Left(presumedSolution.first - pointJumpDistance, presumedSolution.second);

            /// Jump distances
            double dist_Up = globalDistance(presumedSolution_Up);
            double dist_Down = globalDistance(presumedSolution_Down);
            double dist_Right = globalDistance(presumedSolution_Right);
            double dist_Left = globalDistance(presumedSolution_Left);

            /// Current distance
            double dist_Current = globalDistance(presumedSolution);

            if(dist_Current > dist_Up){
                presumedSolution = presumedSolution_Up;
                continue;
            }
            if(dist_Current > dist_Down){
                presumedSolution = presumedSolution_Down;
                continue;
            }
            if(dist_Current > dist_Right){
                presumedSolution = presumedSolution_Right;
                continue;
            }
            if(dist_Current > dist_Left){
                presumedSolution = presumedSolution_Left;
                continue;
            }

            /// If the code reaches this point, it means we've reached the ending point
            break;
        }
        pointJumpDistance /= 4;
    }
    out<<presumedSolution.first<<" "<<presumedSolution.second;

    return 0;
}