2131. [JLOI 2014]镜面通道

镜面通道

题目背景:

掩体纪元 5 年，星环公司宣布曲率驱动飞船计划，你奉命清理大型激光切割器的镜面通道。

题目描述:

在一个二维平面上，有一个镜面通道，由镜面AC，BD组成，AC，BD长度相等，且都平行于x轴，B位于(0, 0)。

通道中有n个外表面为镜面的光学元件，光学元件α为圆形，光学元件β为矩形(这些元件可以与其他元件和通道有交集，具体看下图)。

光线可以在AB上任一点以任意角度射入通道，光线不会发生削弱。当出现元件与元件，元件和通道刚好接触的情况视为光线无法透过(比如两圆相切)。现在给出通道中所有元件的信息(α元件包括圆心坐标和半径xi，yi，ri，β元件包括左下角和右上角坐标x1，y1，x2，y2)

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

当然，显然存在光线无法透过的情况，现在交给你一个艰巨的任务，请求出至少拿走多少个光学元件后，存在一条光线线路可以从CD射出。

下面举例说明：

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

输入格式:

第一行包含两个整数, x , y ,表示C点坐标。

第二行包含一个整数, n ，表示有n个光学元件。

接下来 n 行:

第一个数字 ti 表示这个元件的类型。

如果 ti = 1，表示元件α，后面会有三个整数xi，yi，ri分别表示圆心坐标和半径。

如果 ti = 2，表示元件β，后面会有四个整数x1，y1，x2，y2分别表示左下角和右上角坐标（矩形都平行，垂直于坐标轴）

输出格式:

输出包含两行:

第一行一个整数，至少需要拿走的光学元件个数m。

第二行，接下来 m 个数, 输出要拿走的光学元件的编号。如果有多组方案输出字典序最小的即可。

样例数据:

数据范围及约定:

保证给定点的坐标在矩形ABDC内(包括边界)。