Cod sursa(job #49145)

Utilizator gigi_becaliGigi Becali gigi_becali Data 5 aprilie 2007 13:45:17
Problema Adapost 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <cstdio>
#include <ctime>
#include <cstdlib>
#define maxn 50004
struct point { double x, y;};
int n;
point x[maxn];

void citire()
{
	freopen("adapost2.in", "r", stdin);
	scanf("%d\n", &n);
	for(int i=1;i<=n;i++) scanf("%lf %lf\n", &x[i].x, &x[i].y);
}

double dist(double mx, double my)
{
	int i;
	double sum=0;
	for(i=1;i<=n;i++) sum+=(mx-x[i].x)*(mx-x[i].x)+(my-x[i].y)*(my-x[i].y);
	return sum;
}

void solve()
{
	int i, j;
	int Mx=-10000, My=-10000;
	point p;
	p.x=((rand()%6667777)%1000000)/1000.0;
	p.y=((rand()%6667777)%1000000)/1000.0;
	
	p.x=p.y=0;
	for(i=1;i<=n;i++) p.x+=x[i].x, p.y+=x[i].y;
	p.x=p.x/(double) n;
	p.y=p.y/(double)n;
	
	for(i=1;i<=n;i++)
	{
		if(p.x>Mx) Mx=(int)p.x;
		if(p.y>My) My=(int)p.y;
	}
	
	Mx++;
	My++;
	Mx*=1000, My*=1000;
	point best;
	double sbest=0x3f3f3f3f;
	int ntimes=1000;
	double rx, ry;
	for(int k=0;k<ntimes;k++)
	{
		
		rx=((rand()%6667777)%Mx)/1000.0;
		ry=((rand()%6667777)%My)/1000.0;
		double s=dist(rx, ry);
		if(s<sbest) sbest=s, best.x=rx, best.y=ry;
	//printf("%f %f %f\n", rx, ry, s);
	}
	freopen("adapost2.out", "w", stdout);
	printf("%f %f\n", best.x, best.y);
//	printf("%f\n", dist(4.1442, 4.2898));
}



int main()
{
	time_t s;
	time(&s);
	srand(s%666013);
	
	citire();
	solve();
	return 0;
}