Cod sursa(job #2066453)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 15 noiembrie 2017 00:47:30
Problema Adapost 2 Scor 40
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.53 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< int , int > PII;

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

ll check(int x, int y){
	int 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); cin.tie(0); cout.tie(0);
    ifstream cin("adapost2.in");
    ofstream cout("adapost2.out");
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> x >> y;
		a[i] = {x * 1000, y * 1000};
		px += a[i].x;
		py += a[i].y;
	}
	px /= n; py /= n; //stabilesc o pozitie de start optima
	ll CURR = check(px, py);
	double pas = 1000;
	while (pas >= 0.00001){
		ll R = check(px + pas, py), RU = check(px + pas, py + pas);
		ll L = check(px - pas, py), LU = check(px - pas, py + pas);
		ll U = check(px, py + pas), LD = check(px - pas, py - pas);
		ll D = check(px, py - pas), RD = check(px + pas, py - pas);
		if (min({R, L, U, D, RU, RD, LU, LD}) >= CURR){pas /= 2; continue;}
		ll mn = min({R, L, U, D, RU, RD, LU, LD});
		px += (R == mn || RU == mn || RD == mn ? pas : (L == mn || LU == mn || LD == mn ? -pas : 0));
		py += (U == mn || RU == mn || LU == mn ? pas : (D == mn || LD == mn || RD == mn ? -pas : 0));
		CURR = mn;
		pas += 250;
	}
	cout << setprecision(4) << fixed << px / 1000.0 << " " << py / 1000.0;
}