← 返回题目列表

Codeforces · 33/D

D. 骑士

中文机器翻译题面 查看原题

Berland再次面临黑暗时期。邪恶领主范德马特的军队即将征服整个王国。贝尔兰国王瓦列里·严酷召集的战争委员会中来了多名骑士。经过长时间的讨论,我们发现王国恰好有 n 个控制点(如果敌人至少占领其中一个控制点,则战争失败),并且每个骑士将占领其中一个控制点。

Berland被分为m + 1个区域,有m个栅栏,从一个区域到另一个区域的唯一方法就是翻过栅栏。每个栅栏都是平面上的一个圆,没有两个栅栏有公共点,并且栅栏上没有控制点。给定 k 对数字 ai、bi。对于每一对,你必须找出:来自索引为ai的控制点的骑士必须爬过多少栅栏才能到达控制点bi(以防范德马特首先攻击控制点bi)。由于每个骑士都骑着一匹马(将马扔过栅栏非常困难),因此您需要找出每对骑士需要翻越的最少栅栏数量。

输入

第一输入行包含三个整数 n、m、k (1 ≤ n, m ≤ 1000, 0 ≤ k ≤ 100000)。然后n行,每行包含两个整数Kxi,Kyi(- 109≤Kxi,Kyi≤109)——索引为i的控制点的坐标。控制点可以重合。

以下 m 行中的每一行都用三个整数 ri、Cxi、Cyi (1 ≤ ri ≤ 109, - 109 ≤ Cxi, Cyi ≤ 109) 描述索引为 i 的栅栏 - 相应栅栏所在圆的半径和圆心。

然后跟随 k 对整数 ai, bi (1 ≤ ai, bi ≤ n),每个在单独的行中 - 要求你必须回答。 ai 和 bi 可以重合。

输出

准确输出 k 行,每行包含一个整数——对应请求的答案。

示例

输入 #1

2 1 1
0 0
3 3
2 0 0
1 2

输出 #1

1

输入 #2

2 3 1
0 0
4 4
1 0 0
2 0 0
3 0 0
1 2

输出 #2

3