Cod sursa(job #1053703)

Utilizator Robert29FMI Tilica Robert Robert29 Data 12 decembrie 2013 21:51:01
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.2 kb
#include<stdio.h>
#include<math.h>
FILE*f = fopen("adapost2.in", "r");
FILE*g = fopen("adapost2.out", "w");
int n;
struct punct
{
	double x, y;
} v[50001];
double dist(double x, double y)
{
	return sqrt(y*y + x*x);
}
double calc(double x, double y)
{
	double sum = 0;
	for (register int i = 1; i <= n; ++i)
		sum += dist(x - v[i].x, y - v[i].y);
	return sum;
}
double min(double a, double b)
{
	if (a<b)
		return a;
	return b;
}
int main()
{
	fscanf(f, "%d", &n);
	double x, y, p;
	for (int i = 1; i <= n; ++i){
		fscanf(f, "%lf%lf", &v[i].x, &v[i].y);
		x += v[i].x;
		y += v[i].y;
	}

	x /= n;
	y /= n;
	p = 200;
	double sum = calc(x, y);
	while (p >= 0.0005)
	{

		double sum1, sum2, sum3, sum4;

		sum1 = calc(x + p, y);
		if (sum1<sum)
		{
			x += p;
			sum = sum1;
			continue;
		}

		sum1 = calc(x - p, y);
		if (sum1<sum)
		{
			x -= p;
			sum = sum1;
			continue;
		}

		sum1 = calc(x, y - p);
		if (sum1<sum)
		{
			y -= p;
			sum = sum1;
			continue;
		}

		sum1 = calc(x, y + p);
		if (sum1<sum)
		{
			y += p;
			sum = sum1;
			continue;
		}

		p /= 2;
	}

	fprintf(g, "%.4lf %.4lf", x, y);

	fclose(f);
	fclose(g);
	return 0;
}