Cod sursa(job #2066481)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 15 noiembrie 2017 01:32:41
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>
#define pb push_back 
#define x first 
#define y second 
#define mod 1000000007LL
using namespace std;
typedef long long ll;
typedef pair< double , double > PII;

int n;
double x, y, px, py;
PII a[50005];
	
double dist(double x, double y, double xx, double yy){
	return sqrt((xx - x) * (xx - x) + (yy - y) * (yy - y));
}

double check(double x, double y){
	double rs = 0;
	for (int i = 1; i <= n; i++)
		rs += dist(x, y, a[i].x, a[i].y);
	return rs;
}	
	
int main(){
	ios_base::sync_with_stdio(0);
    freopen("adapost2.in", "r", stdin);
    freopen("adapost2.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		scanf("%lf%lf", &x, &y);
		a[i] = {x * 1000.0, y * 1000.0};
		px += a[i].x;
		py += a[i].y;
	}
	px /= (double)n; py /= (double)n; //stabilesc o pozitie de start optima
	double CURR = check(px, py), pas = 100000.000;
	while (pas >= 1){
		double R = check(px + pas, py);
		double L = check(px - pas, py);
		double U = check(px, py + pas);
		double D = check(px, py - pas);
		if (R < CURR){ CURR = R, px += pas; continue; }
		if (L < CURR){ CURR = L, px -= pas; continue; }
		if (U < CURR){ CURR = U, py += pas; continue; }
		if (D < CURR){ CURR = D, py -= pas; continue; }
		pas *= 0.6;
	}
	px /= 1000.0, py /= 1000.0;
	printf("%.4lf %.4lf", px, py);
}