Pagini recente » Cod sursa (job #1020424) | Cod sursa (job #2590355) | Solutii Autumn Warmup, Runda 3 | Cod sursa (job #2613237) | Cod sursa (job #2061606)
#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;
}