Cod sursa(job #1802603)

Utilizator Vally77FMI Calinescu Valentin Gelu Vally77 Data 10 noiembrie 2016 15:12:18
Problema Adapost 2 Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
//#include <iostream>
#include <iomanip>
#include <fstream>
#include <math.h>
#include <algorithm>
using namespace std;
ifstream ka("adapost2.in");
ofstream ki("adapost2.out");

const int N_MAX = 50000;

int n;

struct punct
{
	double x, y;
	bool operator < (const punct arg) const
	{
		if(x == arg.x)
			return y < arg.y;
		else
			return x < arg.x;
	}
}puncte[N_MAX + 1];

double abs(double t)
{
	if(t < 0)
		return -t;
	else
		return t;
}

double patrat(double t)
{
	return t * t;
}

double distanta(punct p1, punct p2)
{
	return sqrt(patrat(p1.x - p2.x) + patrat(p1.y - p2.y));
}

punct cautare()
{
	punct p;
	p.x = puncte[1].x;
	p.y = puncte[1].y;
	double pas = 10000.0;
	while(pas - 0.0001 > 0)
	{
		punct pp;
		//cout << p.x << " " << p.y << '\n';		

		pp.x = p.x + pas;
		pp.y = p.y;
		double dist_min = 3000000;
		double dist = 0;
		int aia;
		for(int i = 1; i <= n; i++)
			dist += distanta(pp, puncte[i]);
		if(dist < dist_min)
		{
			dist_min = dist;
			aia = 1;
		}

		pp.x = p.x;
		pp.y = p.y + pas;
		dist = 0;
		for(int i = 1; i <= n; i++)
			dist += distanta(pp, puncte[i]);
		if(dist < dist_min)
		{
			dist_min = dist;
			aia = 2;
		}

		pp.x = p.x - pas;
		pp.y = p.y;
		dist = 0;
		for(int i = 1; i <= n; i++)
			dist += distanta(pp, puncte[i]);
		if(dist < dist_min)
		{
			dist_min = dist;
			aia = 3;
		}

		pp.x = p.x;
		pp.y = p.y - pas;
		dist = 0;
		for(int i = 1; i <= n; i++)
			dist += distanta(pp, puncte[i]);
		if(dist < dist_min)
		{
			dist_min = dist;
			aia = 4;
		}
		
		if(aia == 1)
			p.x += pas;
		else if(aia == 2)
			p.y += pas;
		else if(aia == 3)
			p.x -= pas;
		else
			p.y -= pas;
		pas /= 2;
	}
	return p;
}

int main()
{
	ka >> n;
	for(int i = 1; i <= n; i++)
		ka >> puncte[i].x >> puncte[i].y;
	sort(puncte + 1, puncte + n);
	punct pp = cautare();	
	ki << fixed << setprecision(4) << pp.x << " " << pp.y;
}