В этой теме нет ответов

[lfif]

Задача №541. Столица (informatics)

В некотором царстве, в некотором государстве было N городов, и все они, судя по главной карте императора, имели целые координаты. В те годы леса были дремучие, дороги же строить умели только параллельно осям координат, так что расстояние между двумя городами определялось как |x1 - x2| + |y1 - y2|.
Император решил построить N+1-ый город и сделать его столицей своего государства, при этом координаты столицы также должны быть целыми. Место для столицы следует выбрать так, чтобы среднее арифметическое расстояний между столицей и остальными городами было как можно меньше. Однако, разумеется, столицу нельзя строить на месте существующего города.
Нелегкая задача выбрать место для столицы поручена Вам.

Входные данные
В первой строке вводится число N - количество городов (1 <= N <= 100). Следующие N строк содержат координаты городов - пары целых чисел, не превышающих 1000 по абсолютной величине.

Выходные данные
Выведите два целых числа - координаты точки, где следует построить столицу. Если решений несколько, выведите любое.

входные данные
8
0 0
1 0
2 0
0 1
2 1
0 2
1 2
2 2

выходные данные
1 1

входные данные
4
0 0
1 1
0 1
1 0

выходные данные
0 -1

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define F first
#define S second
using namespace std;
const int N = 1000;
int x[N], y[N];
int r[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int32_t main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	int n;
	cin >> n;
	set <pair <int, int>> st;
	for (int i = 0; i < n; ++i) {
    	int a, b;
    	cin >> a >> b;
    	st.insert({a, b});
    	x[i] = a;
    	y[i] = b;
	}
	sort(x, x + n);
	sort(y, y + n);
	int xx = x[n / 2], yy = y[n / 2], ans = 2e15 + 7; // нахождение центральной манхеттанской точки
	if (st.count({xx, yy}) > 0) { // если центральная точка занята
    	for (auto to : st){
        	for (int k = 0; k < 4; ++k) { // проверка 4 соседей каждого заданного города
            	int x1 = to.F + r[k][0], y1 = to.S + r[k][1];
            	int dist = 0;
            	if (st.count({x1, y1}) > 0) continue;
            	for (auto now : st) { // нахождение суммы минимальных расстояний до всех городов от (x1, y1)
                	int x2 = now.F, y2 = now.S;
                	dist += abs(x1 - x2) + abs(y1 - y2);
            	}
            	if (dist < ans) { // выбор лучшей суммы
                	ans = dist;
                	xx = x1; yy = y1;
            	}
        	}
    	}
	}
	cout << xx << ' ' << yy;
	return 0;
}

Автор статьи: Андреева Даша