| Codeforces Round 103 (Div. 2) |
|---|
| Закончено |
Самое Секретное Совещание Самой Секретной Военной Части проходит в Самом Секретном Месте — на бесконечной плоскости, в которой введена декартова система координат. Стол для переговоров представляет собой прямоугольник со сторонами параллельными осям координат и с вершинами в целочисленных точках плоскости. В каждой целочисленной точке, которая принадлежит периметру стола, находится кресло, где сидит один из генералов.
Чтобы генералам было не холодно в зимнее время, в некоторых точках на плоскости стоят тепловые батареи. Каждая батарея характеризуется числом ri — радиусом действия. То есть если некоторый генерал находится на расстоянии, меньшем или равном ri от этой батареи — то ему комфортно и тепло. В этой задаче под расстоянием следует понимать Евклидово расстояние: расстояние от точки (x1, y1) до точки (x2, y2) равно 
Каждый генерал, который находится вне зон действия всех батарей, может заболеть, и поэтому вы должны принести ему теплый плед. Ваша задача — подсчитать, сколько теплых пледов вам нужно принести в Самое Секретное Место.
Генералам, которым уже комфортно, не требуется плед. Также генералы никогда не перегреваются, даже если они находятся в зоне действия нескольких батарей. Батареи могут быть расположены в любых целочисленных точках плоскости: даже внутри прямоугольника (под столом) и на периметре (непосредственно под одним из генералов), — и даже в этих случаях их радиус действия не меняется.
В первой строке даны координаты двух противоположных углов стола xa, ya, xb, yb (xa ≠ xb, ya ≠ yb). Во второй строке дано число n — количество батарей (1 ≤ n ≤ 103), и далее в n строках даны координаты батарей в формате «xi yi ri», числа разделены пробелом. Все числа во входных данных — целые. Все координаты по модулю не превосходят 1000, 1 ≤ ri ≤ 1000. В одной точке могут находиться несколько батарей.
Выведите единственное число — сколько вам нужно принести пледов.
2 5 4 2
3
3 1 2
5 3 1
1 3 2
4
5 2 6 3
2
6 2 2
6 5 3
0
В первом примере генералы сидят в точках: (2, 2), (2, 3), (2, 4), (2, 5), (3, 2), (3, 5), (4, 2), (4, 3), (4, 4), (4, 5). Из них вне зон действия батарей расположены лишь 4, это генералы в точках: (2, 5), (3, 5), (4, 4), (4, 5).
Во втором примере генералы сидят в точках: (5, 2), (5, 3), (6, 2), (6, 3). Каждый из них находится в зоне действия хотя бы одной батареи, и пледы не нужны вообще.
