Решение задачи Новый год и местоположение сокровища с Codeforces
Без пояснения   Просмотров: 58
Боб — пират, ищущий величайшее сокровище, которое когда-либо видел мир. Известно, что сокровище расположено в точке T, координаты которой только предстоит узнать.
Боб путешествовал по миру и собирал подсказки о сокровище в n обелисках. Эти подсказки были на древнем языке, и он смог их расшифровать только дома. Поскольку он не знает, какая подсказка принадлежит какому обелиску, поиск сокровища может стать проблемой. Вы можете помочь ему?
Как известно, мир — это двумерная плоскость. i-й обелиск находится в целочисленных координатах (xi,yi). j-я подсказка состоит из 2 целых чисел (aj,bj) и принадлежит обелиску pj, где p — некоторая (неизвестная) перестановка из n элементов. Это означает, что сокровище находится в точке T=(xpj+aj,ypj+bj). Эта точка T должно быть одинакова для всех подсказок.
Другими словами, каждая подсказка принадлежит ровно одному из обелисков, и у каждого обелиска есть ровно одна принадлежащая ему подсказка. Подсказка представляет вектор от обелиска к сокровищу. Подсказки должны быть распределены среди обелисков таким образом, чтобы все они указывали на одну и ту же позицию сокровища.
Ваша задача — найти координаты клада. Если существует несколько решений, вы можете вывести любое из них.
Обратите внимание, что вам не нужно находить перестановку. Перестановки используются только для объяснения задачи.
Боб путешествовал по миру и собирал подсказки о сокровище в n обелисках. Эти подсказки были на древнем языке, и он смог их расшифровать только дома. Поскольку он не знает, какая подсказка принадлежит какому обелиску, поиск сокровища может стать проблемой. Вы можете помочь ему?
Как известно, мир — это двумерная плоскость. i-й обелиск находится в целочисленных координатах (xi,yi). j-я подсказка состоит из 2 целых чисел (aj,bj) и принадлежит обелиску pj, где p — некоторая (неизвестная) перестановка из n элементов. Это означает, что сокровище находится в точке T=(xpj+aj,ypj+bj). Эта точка T должно быть одинакова для всех подсказок.
Другими словами, каждая подсказка принадлежит ровно одному из обелисков, и у каждого обелиска есть ровно одна принадлежащая ему подсказка. Подсказка представляет вектор от обелиска к сокровищу. Подсказки должны быть распределены среди обелисков таким образом, чтобы все они указывали на одну и ту же позицию сокровища.
Ваша задача — найти координаты клада. Если существует несколько решений, вы можете вывести любое из них.
Обратите внимание, что вам не нужно находить перестановку. Перестановки используются только для объяснения задачи.