Cod sursa(job #1846025)

Utilizator ASD135Radu M ASD135 Data 12 ianuarie 2017 01:21:39
Problema Adapost 2 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream>
#include <cmath>
#include <map>
using namespace std;

const int Q=50007;

int n;

struct point
{
	double x,y;
}v[Q];

std::map<double, map<double,double> > prec;


static double aux,dist_act,gx,gy,pas;

double dist(double a, double b)
{
	double rez=0;
	for(int i=1; i<=n; i++)
	{
		rez+=sqrt((a-v[i].x)*(a-v[i].x) + (b-v[i].y)*(b-v[i].y));
		if(rez>dist_act)
			return rez;
	}
	return rez;
}


bool inline bra1()
{
	int sgn=rand()&1;
	sgn*=2;
	sgn--;


	aux=dist(gx,gy+sgn*pas);
	if(aux<dist_act)
	{
		gy+=sgn*pas;
		dist_act=aux;
		return 1;
		
	}
	else
	{
		aux=dist(gx,gy-sgn*pas);
		if(aux<dist_act)
		{
			gy-=sgn*pas;
			dist_act=aux;
			return 1;
		}
	}
	return 0;
}

bool inline bra2()
{
	int sgn=rand()&1;
	sgn*=2;
	sgn--;

	aux=dist(gx+pas*sgn,gy);
		if(aux<dist_act)
		{
			gx+=pas*sgn;
			dist_act=aux;
			return 1;
		}
		else
		{
			aux=dist(gx-sgn*pas,gy);
			if(aux<dist_act)
			{
				gx-=sgn*pas;
				dist_act=aux;
				return 1;
			}	
		}

	return 0;
}

int main()
{
	freopen("adapost2.in","r",stdin);
	freopen("adapost2.out","w",stdout);
	cin>>n;

	gx=0,gy=0;

	for(int i=1; i<=n; i++)
	{
		cin>>v[i].x>>v[i].y;
		gx+=v[i].x;
		gy+=v[i].y;
	}

	gx/=n;
	gy/=n;

	 pas=1<<9;

	aux,dist_act=dist(gx,gy);

	for(int tmp=1; tmp<=40; tmp++)
	{
		if(rand()&1)
		{
			if(bra1());
			else if( bra2());
			else pas/=2;
		}
		else
		{
			if (bra2());
			else if( bra1());
			else pas/=2;
		}
		if(pas<0.001)
			break;
	}

	printf("%.6lf %.6lf\n",gx,gy);

	return 0;
}