Cod sursa(job #1846166)

Utilizator heracleRadu Muntean heracle Data 12 ianuarie 2017 11:55:34
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <iostream>
#include <cmath>
#include <map>
using namespace std;



///parsare

bool digit[200];


const int SBUF=4096;
char BUF[SBUF];
int pbuf=SBUF;

char get_char()
{
	if(pbuf==SBUF)
	{
		pbuf=0;
		fread(BUF,SBUF,1,stdin);
	}
	return BUF[pbuf++];
}

char x;

int get_int()
{
	x=get_char();

	while(digit[x]==0)
		x=get_char();

	int rez=0;

	while(digit[x])
	{
		rez=rez*10+x-'0';
		x=get_char();
	}

	return rez;
}

int zece[8];

double get_double()
{
	x=get_char();

	while(digit[x]==0)
		x=get_char();

	int rez=0;

	while(digit[x])
	{
		rez=rez*10+x-'0';
		x=get_char();
	}
	if(x=='.')
	{
		int rez2=0;
		x=get_char();

		int cont=0;

		while(digit[x])
		{
			rez2=rez2*10+x-'0';
			cont++;
			x=get_char();
		}

		double fin=rez2;
		fin/=zece[cont];
		fin+=rez;
		return fin;
	}
	else
		return rez;
}

void jibril()
{
	zece[0]=1;
	for(int i=1; i<=8; i++)
	{
		zece[i]=zece[i-1]*10;
	}

	for(int i='0'; i<='9'; i++)
	{
		digit[i]=1;
	}
}

///parsare

const int Q=50007;

int n;

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




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));
	}
	return rez;
}


int main()
{
	jibril();
	freopen("adapost2.in","r",stdin);
	freopen("adapost2.out","w",stdout);
	n=get_int();


	double dist_act,gx,gy,pas;

	gx=0,gy=0;

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

	gx/=n;
	gy/=n;

	pas=1<<9;
	double sus,jos,st,dr;

	double d1,d2;

	for(int tmp=1; tmp<=50; tmp++)
	{
		dist_act=dist(gx,gy);
		sus=dist(gx+pas,gy);
		jos=dist(gx-pas,gy);
		st=dist(gx,gy-pas);
		dr=dist(gx,gy+pas);

		if(sus<dist_act && st>dist_act && dr>dist_act)
		{
			gx+=pas;
			continue;
		}
		if(jos<dist_act && st>dist_act && dr>dist_act)
		{
			gx-=pas;
			continue;
		}
		if(st<dist_act && sus>dist_act && jos>dist_act)
		{
			gy-=pas;
			continue;
		}
		if(dr<dist_act && sus>dist_act && jos>dist_act)
		{
			gy+=pas;
			continue;
		}
		if(sus<dist_act && st<dist_act)
		{
			d1=dist_act-sus;
			d2=dist_act-st;
			gx+=d1/(d1+d2) * pas;
			gy-=d2/(d1+d2) * pas;
			continue;
		}
		if(jos<dist_act && st<dist_act)
		{
			d1=dist_act-jos;
			d2=dist_act-st;
			gx-=d1/(d1+d2)*pas;
			gy-=d2/(d1+d2)*pas;
			continue;
		}
		if(sus<dist_act && dr<dist_act)
		{
			d1=dist_act-sus;
			d2=dist_act-dr;
			gx+=d1/(d1+d2)*pas;
			gy+=d2/(d1+d2)*pas;
			continue;
		}
		if(jos<dist_act && dr<dist_act)
		{
			d1=dist_act-jos;
			d2=dist_act-dr;
			gx-=d1/(d1+d2)*pas;
			gy+=d2/(d1+d2)*pas;
			continue;
		}
		pas/=2;

		if(pas<0.001)
			break;

	}

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

	return 0;
}