проблема в том, что таких точек бесконечное множество (если я правильно понял условие). Следовательно найдя определённую точку довольно сложно быть стопудово уверенным, что это та самая точка и более правильного решения быть не может.

Значит надо искать то самое множество, а потом уже наобум брать оттуда какую-нибудь точку.

Следовательно тут надо мутить со множествами, их пересечениями и объединениями. Это программа первого курса, а я на четвёртом - у меня проблемы, ни хрена уже не помню...

Но преполагаю, что надо так: сначала смотрим на ось Ох (или Оу). Потом проецируем все прямоугольники на неё и пробиваем самую "чёрную" область, то есть область в которой пересекается наибольшее количество прям-ков.

Потом делаем то же с другой осью и ищем пересечение этих "чёрных" областей. Полученный прям-к будет скоплением искомых точек. Выбирай середину - не ошибёшся .

Самое сложное здесь: определить самую "чёрную" область, но и это не представляет особых проблем. Алгоритм типа:

1) находим самую правую левую сторону прям-ка.

2) находим самую левую правую сторону прям-ка.

3) если (1) левее (2), то всё в порядке, иначе (1)=(первая влево от (1)). goto (3).

4) наше "чёрное" место находится между (1) и (2).

Конечно, требует шлифовки, но незаинтересованному в результате, мне не особо хочется тратить столько сил на его реализацию. В общих чертах решил и всё! Вот если бы какой конкурс замутили, тогда...  

Ответить

Если я правильно понял, задача элементарная. Создаем массив NxN, где границы между ячейками - сортированные координаты вершин прямоугольников. Затем по очереди "зарисовываем" прямоугольники, увеличивая ячейки на 1. А потом просто ищем максимум, получаем из координат ячейки координаты соответствующего "элементарного прямоугольника", берем, например, его центр и выдаем... Совсем несложная задача...

Ответить

To Sharp: не совсем понял эту фразу:

границы между ячейками - сортированные координаты вершин прямоугольников

но если я правильно понял, то возражение - у нас ведь координатная плоскость. Соот-но один прямоуг-к может иметь порядок координат 10^234123412341234 (!!!), а другой

10^(-235623542345234). Это я, конечно, утрирую (хотелось бы посмотреть на переменные такого порядка), но массивы, ИМХО, здесь не полезут - надо чисто сравнением: что больше, а что меньше...

Ответить

В олимпиадах всегда ставится ограничение на тип данных 10^(817262346) степени тебе никто не даст, если сам не попросишь. К тому же написано, что координаты - вещественные числа, что обозначает, что следует использовать тип double.

Что же касается мутной фразы "отсортированный массив координат точек вершин", понять ее несложно. Имеем два прямоугольника (-1.0,-1.0 - 1.0,1.0) и (0,0 - 2,2). Сортируем массив координат вершин по X-ам и Y-ам, получаем два массива: X-ов: {-1.0,0.0,1.0,2.0} и Y-ов: {-1.0,0.0,1.0,2.0}. Затем объявляем массив 3*3 (понятно, что он не может быть больше 2*N x 2*N), после чего просто заполняем его ячейки, инкрементируя их содержимое так, как расположены прямоугольники. Т.е.:

после 1-го прям-ка:

0 0 0

1 1 0

1 1 0

после 2-го:

0 1 1

1 2 1

1 1 0

Ищем максимум: 2 - находится (тут-то и понадобятся сохраненные раньше отсортированные X и Y) между 0 и 1 по Ox и между 0 и 1 по Oy. Возьмем центральную точку этого прямоугольника - 0.5,0.5 - она будет искомой точкой.

Ответить

Sharp, ты будешь смеяться, но в принципе я имел ввиду то же самое. Твоя двойка - моя "чёрная" зона...

Ответить

Ответить

Ответить

Ответить

Ответить

Ответить