eolymp
Задачі

Дерева

Дерева

У столиці країни Олімпія було визначено територію для будівництва нового Олімпійського парку. Границі території мають форму опуклого багатокутника. Ідея дизайнера парку полягає в тому, щоб засадити деревами певну кількість зелених зон, які мають на карті форму круга: кожну зелену зону можна задати координатами центра та її радіусом.

Отже, дизайнер доручив посадити дерева у точках, що мають цілі координати та розташовані в межах парку (можливо, на його границі) та хоча б однієї з зелених зон (можливо, на межі). Якщо певні зелені зони перетинаються, тобто одна й та сама точка на карті належить двом чи більше зеленим зонам, у цьому місці тим не менш можна посадити лише одне дерево.

Завдання

Напишіть програму, що за даними про координати вершин многокутника, який задає територію парку, даними про координати центрів та радіуси зелених зон визначить кількість дерев, які має бути посаджено.

Вхідні дані

У першому рядку вхідного файла вказано ціле число N (3 ≤ N ≤ 105) — кількість вершин багатокутника, що задає територію парку. Наступні N рядків містять по два цілих числа — відповідно абсциси та ординати вершин у порядку обходу за чи проти годинникової стрілки. Наступний рядок містить ціле число M (1 ≤ M ≤ 50 000) — кількість зелених зон. Далі йдуть M рядків, кожен з яких містить по три цілих числа: абсцису та ординату центра зеленої зони, а також її радіус. Усі координати, задані у вхідному файлі, є цілими числами в межах від-109 до 109 включно. Радіуси зелених зон цілі додатні, сума всіх радіусів не перевищує 105. Зверніть увагу, що деякі зелені зони можуть цілком лежати всередині інших зон; крім того, окремі зелені зони можуть лежати поза многокутником. Різні зони можуть мати спільні центри або й узагалі збігатися.

Вихідні дані

Єдиний рядок вихідного файла повинен містити єдине ціле число — кількість дерев, що будуть посаджені за дорученням дизайнера.

Оцінювання

Набір тестів складається з блоків, для яких додатково виконуються такі умови:

1. 60 % балів: N ≤ 100. Зокрема, серед даного набору є такі групи тестів, що перетинаються:

  • 20 % балів (від загальної кількості): парк має форму прямокутника, сторони якого паралельні осям координат.
  • 30 % балів (від загальної кількості): N*M*R2 ≤ 107, де через R позначено найбільший з радіусів.
  • 25 % балів (від загальної кількості): існує квадрат зі сторонами довжини 2015, паралельними до осей координат, у якому або на межах якого повністю лежить територія парку.

40 % балів: на вхідні дані не накладено додаткових обмежень.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
3
0 0
15 0
15 15
3
3 3 4
5 5 7
15 15 1
Вихідні дані #1
73
Джерело XXVIII Всеукраїнська олімпіада з інформатики 2015 р.