Cod sursa(job #3136641)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 7 iunie 2023 13:13:48
Problema Adapost 2 Scor 97
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
//Ilie Dumitru
#include<cstdio>
#include<cmath>
const int NMAX=50005;

struct pos
{
	double x, y;
};

int N;
pos v[NMAX];

inline double getDist(pos a, pos b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double getTotalDistance(pos p)
{
	int i;
	double d=0;

	for(i=0;i<N;++i)
		d+=getDist(p, v[i]);

	return d;
}

pos getBest()
{
	double x=500, y=500, nx, ny;
	double v;
	double currDist=getTotalDistance({x, y}), aux;

	for(v=500;v>=0.001;v*=0.5)
	{
		nx=x+v;
		ny=y;
		aux=getTotalDistance({nx, ny});
		if(aux<currDist)
		{
			currDist=aux;
			x=nx;
			y=ny;
		}
		else
		{
			nx=x-v;
			ny=y;
			aux=getTotalDistance({nx, ny});
			if(aux<currDist)
			{
				currDist=aux;
				x=nx;
				y=ny;
			}
		}

		nx=x;
		ny=y+v;
		aux=getTotalDistance({nx, ny});
		if(aux<currDist)
		{
			currDist=aux;
			x=nx;
			y=ny;
		}
		else
		{
			nx=x;
			ny=y-v;
			aux=getTotalDistance({nx, ny});
			if(aux<currDist)
			{
				currDist=aux;
				x=nx;
				y=ny;
			}
		}
	}

	return {x, y};
}

int main()
{
	FILE* f=fopen("adapost2.in", "r"), *g=fopen("adapost2.out", "w");
	int i;
	pos ans;

	fscanf(f, "%d", &N);
	for(i=0;i<N;++i)
		fscanf(f, "%lf%lf", &v[i].x, &v[i].y);

	ans=getBest();
	fprintf(g, "%lf %lf\n", ans.x, ans.y);

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