Problem1397--「JLOI2014」镜面通道

1397: 「JLOI2014」镜面通道

[Creator : ]
Time Limit : 1 sec  Memory Limit : 256 MB

Description

在一个二维平面上,有一个镜面通道,由镜面 ACACACBDBDBD 组成,ACACACBDBDBD 长度相等,且都平行于 xxx 轴,BBB 位于 (0,0)(0,0)(0,0)。通道中有 nnn 个外表面为镜面的光学元件,光学元件 α\alphaα 为圆形,光学元件 β\betaβ 为矩形(这些元件可以与其他元件和通道有交集,具体看下图)。光线可以在 ABABAB 上任一点以任意角度射入通道,光线不会发生削弱。当出现元件与元件,元件和通道刚好接触的情况视为光线无法透过(比如两圆相切)。

如上图,S到T便是一条合法线路。

当然,显然存在光线无法透过的情况,下面举例说明:

现在假设,取走中间那个矩形,那么就可以构造出一条穿过通道的光路,如图中的S到T。

现在给出通道中所有元件的信息(α\alphaα 元件包括圆心坐标和半径 (xi,yi),ri(x_i,y_i),r_i(xi,yi),riβ\betaβ 元件包括左下角和右上角坐标 (x1,y1),(x2,y2)(x_1,y_1),(x_2,y_2)(x1,y1),(x2,y2)),并交给你一个艰巨的任务:请求出至少拿走多少个光学元件后,存在一条光线线路可以从CD射出。

输入格式

第一行包含两个整数,xxxyyy,表示 CCC 点坐标。
第二行包含一个数字,nnn,表示有 nnn 个光学元件。
接下来 nnn 行表示元件信息。
第一个数字如果是 1,表示为元件 α\alphaα,其后有三个整数 xi,yi,rix_i,y_i,r_ixi,yi,ri 分别表示圆心坐标和半径。
第一个数字如果是 2,表示为元件 β\betaβ,其后有四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2x1,y1,x2,y2 分别表示左下角和右上角坐标(矩形都平行,垂直于坐标轴)。

输出格式

输出包含一行,至少需要拿走的光学元件个数 mmm

样例

样例输入

1000 100
6
1 500 0 50
2 10 10 20 100
2 100 10 200 100
2 300 10 400 100
2 500 10 600 100
2 700 0 800 100

样例输出

2

数据范围与提示

对于所有数据,x≤100000, y≤1000, n≤300x \leq 100000,\ y \leq 1000,\ n \leq 300x100000, y1000, n300

Source/Category