| Codeforces Round 203 (Div. 2) |
|---|
| Закончено |
Император Палпатин очень любит сов. У Императора есть чертеж новой Звезды Смерти, на котором нарисовано n различных отрезков и m различных окружностей. Будем полагать, что отрезки пронумерованы от 1 до n некоторым образом, и окружности пронумерованы от 1 до m некоторым образом.
Совой, по мнению Палпатина, является совокупность пары различных окружностей (i, j) (i < j) и одного отрезка k такая, что:
- окружности i и j симметричны относительно прямой, содержащей отрезок k;
- окружности i и j не имеют общих точек;
- окружности i и j имеют одинаковый радиус;
- отрезок k пересекается с отрезком, соединяющем центры окружностей i и j.
Помогите Палпатину, посчитайте количество различных сов на рисунке.
В первой строке записаны два целых числа — n и m (1 ≤ n ≤ 3·105, 2 ≤ m ≤ 1500).
Далее в n строках записаны по четыре целых числа x1, y1, x2, y2 — координаты двух концов текущего отрезка. Гарантируется, что каждый отрезок имеет положительную длину.
Затем в m строках записаны по три целых числа xi, yi, ri — координаты центра и радиус i-ой окружности. Все координаты — целые числа, не превосходящие 104 по абсолютной величине. Радиус — целое положительное число, не превосходящее 104.
Гарантируется, что все отрезки и все окружности являются различными.
Выведите единственное число — ответ на задачу.
Пожалуйста, не используйте спецификатор %lld для вывода 64-битных чисел на С++. Рекомендуется использовать поток cout или спецификатор %I64d.
1 2
3 2 3 -2
0 0 2
6 0 2
1
3 2
0 0 0 1
0 -1 0 1
0 -1 0 0
2 0 1
-2 0 1
3
1 2
-1 0 1 0
-100 0 1
100 0 1
0
Это сова из первого примера. Она сидит и ждет, когда вы ее посчитаете.
