Cod sursa(job #1824206)

Utilizator andreiulianAndrei andreiulian Data 7 decembrie 2016 15:22:49
Problema Adapost 2 Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<set>
#include<climits>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<bitset>
#define mp make_pair
#define pb push_back
#define ff(i, x, n) for (int i = x; i <= n; ++i)
#define dd(i) cout << i <<'\n'
	#define READ_FROM_FILE
using namespace std;
#ifdef READ_FROM_FILE
	ifstream in("adapost2.in");
	#define cin in
#endif
float x[50005], y[50005];
int n;
double dist(int x0, int y0);
int main(){
	FILE *out = fopen("adapost2.out", "w");
	float sx = 0, sy = 0, R = (1 << 30);
	cin >> n;
	ff(i, 1, n) {
		cin >> x[i] >> y[i];
		sx += x[i]; 
		sy += y[i];
	}
	sx /= n;
	sy /= n;
	bool go;
	double dd, d = 1000;
	while (d >= 1e-6) {
		do {
			go = 0;
			dd = dist(sx - d, sy);
			if (R > dd) {
				R = dd;
				sx = sx - d;
				go = 1;
			} 
			dd = dist(sx, sy + d);
			if (R > dd) {
				R = dd;
				sy = sy + d;
				go = 1;
			} 
			dd = dist(sx + d, sy);
			if (R > dd) {
				R = dd;
				sx = sx + d;
				go = 1;
			} 
			dd = dist(sx, sy - d);
			if (R > dd) {
				R = dd;
				sy = sy - d;
				go = 1;
			} 
		}while (go);
		d /= 2;
	}
	fprintf(out, "%.5f %.5f\n", sx, sy);
	//printf("%.5f %.5f\n", sx, sy);
}
double dist(int x0, int y0) {
	double D = 0;
	ff(i, 1, n) {
		D += sqrt((x0 - x[i]) * (x0 - x[i]) + (y0 - y[i]) * (y0 - y[i]));
	}
	return D;
}