Решение задачи "Новый год и местоположение сокровища" с Codeforces

Без пояснения   Просмотров: 5


Боб — пират, ищущий величайшее сокровище, которое когда-либо видел мир. Известно, что сокровище расположено в точке T, координаты которой только предстоит узнать.

Боб путешествовал по миру и собирал подсказки о сокровище в n обелисках. Эти подсказки были на древнем языке, и он смог их расшифровать только дома. Поскольку он не знает, какая подсказка принадлежит какому обелиску, поиск сокровища может стать проблемой. Вы можете помочь ему?

Как известно, мир — это двумерная плоскость. i-й обелиск находится в целочисленных координатах (xi,yi). j-я подсказка состоит из 2 целых чисел (aj,bj) и принадлежит обелиску pj, где p — некоторая (неизвестная) перестановка из n элементов. Это означает, что сокровище находится в точке T=(xpj+aj,ypj+bj). Эта точка T должно быть одинакова для всех подсказок.

Другими словами, каждая подсказка принадлежит ровно одному из обелисков, и у каждого обелиска есть ровно одна принадлежащая ему подсказка. Подсказка представляет вектор от обелиска к сокровищу. Подсказки должны быть распределены среди обелисков таким образом, чтобы все они указывали на одну и ту же позицию сокровища.

Ваша задача — найти координаты клада. Если существует несколько решений, вы можете вывести любое из них.

Обратите внимание, что вам не нужно находить перестановку. Перестановки используются только для объяснения задачи.

Код

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ll n;
	cin>>n;
	ll s1=0,s2=0;
	for(ll i=1;i<=2*n;i++)
	{
		ll x,y;
		cin>>x>>y;
		s1+=x;s2+=y;
	}
	cout<<s1/n<<" "<<s2/n<<endl;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться