ege-06-Circle-Rectangle-00
Задача
На плоскости задан набор из K объектов. Каждый объект принадлежит к одному из двух типов:
кругу или "простому" прямоугольнику ("простым" назовем прямоугольник со сторонами, параллельными осям координат).
Объект типа круг описывается тремя числами: радиусом и координатами центра.
Объект типа "простой" прямоугольник (далее прямоугольник) описывается четырьмя числами:
координатами противоположных вершин.
Назовем точку A собственной точкой объекта T, если одновременно выполняются условия:
- координаты точки A есть целые числа;
- точка A является внутренней точкой объекта T;
- точка A не является внутренней никакого другого объекта набора
( приналежит только объекту T) .
Считается, что точки на границе объекта этому объекту не принадлежат.
Для каждого объекта типа круг определите количество собственных точек.
В качестве ответа выведите номер объекта с максимальным количеством собственных точек
и количество собственных точек найденного объекта. Если таких объектов несколько, то выведите минимальный номер. (Нумерация объектов в наборе общая и начинается с единицы)
Входные данные
В первой строке записано натуральное число K. (0< K<=100)
Следующие K строк содержат описание объектов (три-четыре целых числаx):
- если числа три, то это объект типа круг и числа обозначают: радиус круга R и координаты центра x, y;
- если числа четыре, то это объект типа прямоугольник и числа обозначают:
координаты противоположных вершин x0, y0, x1,y1;
Все числа по модулю не превосходят 10000, R - натуральное число.
Выходные данные
Два числа - ответ на задание (номер искомого набора, кол-во собственных точек)
Пояснения.
На рисунке представлен набор из двух объектов (круг и прямоугольник)
Данный набор может быть описан с помощью следующих входных данных:
2
5 1 2
8 1 4 7
Вторая строка задает круг радиуса 5 с центром в точке с координатами (1,2)
Третья строка задает прямоугольник с вершинами в точках (8,1); (8.7); (4,7); (4,1)
На рисунке обозначены:
- зелеными крестиками обозначены собственные точки круга;
- оранжевыми плюсами обозначены собственные точки прямоугольника;
- красными кружками обозначены общие целочисленные точки объектов;
- синими кружками обозначены целочисленные точки на границах объектов,
не являющиеся внутренними точками других объектов.
??????Примеры
| Входные данные |
Выходные данные |
Пояснение |
2
5 1 2
8 1 4 7 |
1 66 |
|
2
4 1 8 7
5 1 2 |
2 66 |
Набор объектов не изменился,
но изменилось их описание.
??????? |