#P3630. [JLOI2014]镜面通道

    ID: 2825 传统题 1000ms 128MiB 尝试: 685 已通过: 194 难度: 7 上传者: 标签>难度分类提高+/省选-图论最小割建模拆点限制点容量Dinic最大流最小割定理计算几何圆相交平方距离比较CF2200

[JLOI2014]镜面通道

[JLOI2014] 镜面通道

题目描述

一个镜面通道由两条等长且平行于x轴的镜面组成。 左下角为 B=(0,0)B=(0,0),右上角为 C=(L,H)C=(L,H),通道闭矩形为 [0,L]×[0,H][0,L]\times[0,H]。 光线可从左侧AB上任一点以任意角度进入,目标是从右侧CD射出。

有 nn 个外表面为镜面的光学元件,类型1为圆盘,类型2为边平行坐标轴的矩形。 元件可以相交,也可以跨越通道边界;阻挡及接触只按元件在通道闭矩形中的部分判断。 发生在入口或出口外的交点不计入通道内接触。 闭矩形内元件之间或元件与上下壁相切时,接触处视为不能透过。

求至少移走多少个元件后,存在从左侧进入并从右侧射出的合法光路。

S 至 T 的一条可行反射路径

相交元件连成阻断通道的障碍

移走中间矩形后可以通过的路径

输入格式

第一行两个整数 L,HL,H,即点C的坐标。 第二行一个整数 nn。 接下来 nn 行:

  • 以1开头时,后接圆心坐标及半径 xi,yi,rix_i,y_i,r_i。
  • 以2开头时,后接矩形左下角和右上角坐标 x1,y1,x2,y2x_1,y_1,x_2,y_2。

上述参数均为整数,矩形边平行坐标轴。

输出格式

输出一行一个整数,表示最少移走的元件数。

样例

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

数据范围

1≤L≤1051\le L\le10^5,1≤H≤10001\le H\le1000,1≤n≤3001\le n\le300。