A22532.迷宫

普及/提高-

省选

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小雪和小可可被困在了一个无限大的迷宫中。

已经知道这个迷宫有 NN 堵环状的墙,如果把整个迷宫看作是一个二维平面,那么每一堵墙都是平面上一个圆。任意两个圆不相交,不重合,也不会相切,但有可能相互包含。小雪和小可可分别被困在了 22 个不同的位置,且保证他们的位置与这些圆不重合。

他们只有破坏墙面才能穿过去。

小雪希望知道,如果他们要相见,至少要破坏掉多少堵墙?他们可以在任何位置相见。

输入格式

第一行有一个整数 NN,表示有多少堵墙。

之后 NN 行,每一行有 33 个整数 x,y,rx, y, r,表示有一堵环状的墙是以 (x,y)(x,y) 为圆心,rr 为半径的。

再下一行有一个整数 QQ,表示有多少组询问。

之后 QQ 行,每一行有 44 个整数 a,b,c,da, b, c, d,给出了一组询问,表示小雪所在的位置为 (a,b)(a,b),小可可所在的位置为 (c,d)(c,d)

输出格式

输出 QQ 行,对应 QQ 次询问,每一行输出一个整数,表示最少需要破坏掉多少堵墙才能相见。

输入输出样例

  • 输入#1

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

    输出#1

    2
  • 输入#2

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

    输出#2

    3
    2

说明/提示

0N10000\le N\le 1000

首页