Cod sursa(job #1846142)

Utilizator ASD135Radu M ASD135 Data 12 ianuarie 2017 11:41:54
Problema Adapost 2 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <iostream>
#include <cmath>
#include <map>
using namespace std;

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()
{
	freopen("adapost2.in","r",stdin);
	freopen("adapost2.out","w",stdout);
	cin>>n;


	double dist_act,gx,gy,pas;

	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;
	double sus,jos,st,dr;

	double d1,d2;

	for(int tmp=1; tmp<=200; 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;

	}

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

	return 0;
}