Cod sursa(job #2548169)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 16 februarie 2020 12:43:47
Problema Adapost 2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <bits/stdc++.h>

using namespace std;

class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;
 
	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}
 
public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	
	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
	
	InParser& operator >> (double &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		double sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};

InParser fin("adapost2.in");
ofstream fout("adapost2.out");

const int DIM = 5e4 + 7;

pair <double, double> vec[DIM];

int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};

double dist(double x1, double y1, double x2, double y2)
{
	double ans = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
	ans = sqrt(ans);
	
	return ans;
}

void update(double &x, double &y, double cat, int n, double &best)
{
	int it = -1;
	
	for(int i = 0; i < 8; i++)
	{
		double nx = x + dx[i] * cat;
		double ny = y + dy[i] * cat;
		
		double act = 0;
		
		for(int i = 1; i <= n; i++)
			act += dist(nx, ny, vec[i].first, vec[i].second);
		
		if(act < best)
		{
			best = act;
			it = i;
		}
	}
	
	if(it != -1)
	{
		x += dx[it] * cat;
		y += dy[it] * cat;
	}
}

main()
{
	int n;
	fin >> n;
	
	double x = 0;
	double y = 0;
	
	double best = 0;
	
	for(int i = 1; i <= n; i++)
	{
		fin >> vec[i].first >> vec[i].second;
		
		x += vec[i].first;
		y += vec[i].second;
	}
	
	x /= n;
	y /= n;
	
	for(int i = 1; i <= n; i++)
	{
		best += dist(x, y, vec[i].first, vec[i].second);
	}
	
	double cat = 1000;
	
	for(int pas = 1; pas <= 30; pas++, cat /= 2)
	{
		update(x, y, cat, n, best);
	}
	
	fout << fixed << setprecision(7) << x << ' ' << y << '\n';
}