1301: 「NOI2015」小园丁与老司机
[Creator : ]
Description
小园丁 Mr. S 负责看管一片田野,田野可以看作一个二维平面。田野上有 nnn 棵许愿树,编号 1,2,3,…,n1,2,3, \ldots ,n1,2,3,…,n,每棵树可以看作平面上的一个点,其中第 iii 棵树 (1≤i≤n1 \leq i \leq n1≤i≤n) 位于坐标 (xi,yi)(x_i,y_i)(xi,yi)。任意两棵树的坐标均不相同。
老司机 Mr. P 从原点 (0,0)(0,0)(0,0) 驾车出发,进行若干轮行动。每一轮,Mr. P 首先选择任意一个满足以下条件的方向:
不幸的是,小园丁 Mr. S 发现由于田野土质松软,老司机 Mr. P 的小汽车在每轮行进过程中,都会在田野上留下一条车辙印,一条车辙印可看作以两棵树(或原点和一棵树)为端点的一条线段。
在 Mr. P 之后,还有很多许愿者计划驾车来田野许愿,这些许愿者都会像 Mr. P 一样任选一种最优策略行动。Mr. S 认为非左右方向(即上、左上45∘45^{\circ}45∘ 、右上 45∘45^{\circ}45∘ 三个方向)的车辙印很不美观,为了维护田野的形象,他打算租用一些轧路机,在这群许愿者到来之前夯实所有「可能留下非左右方向车辙印」的地面。
「可能留下非左右方向车辙印」的地面应当是田野上的若干条线段,其中每条线段都包含在某一种最优策略的行进路线中。每台轧路机都采取满足以下三个条件的工作模式:
老司机 Mr. P 从原点 (0,0)(0,0)(0,0) 驾车出发,进行若干轮行动。每一轮,Mr. P 首先选择任意一个满足以下条件的方向:
- 为左、右、上、左上 45∘45^{\circ}45∘ 、右上 45∘45^{\circ}45∘ 五个方向之一。
- 沿此方向前进可以到达一棵他尚未许愿过的树。
不幸的是,小园丁 Mr. S 发现由于田野土质松软,老司机 Mr. P 的小汽车在每轮行进过程中,都会在田野上留下一条车辙印,一条车辙印可看作以两棵树(或原点和一棵树)为端点的一条线段。
在 Mr. P 之后,还有很多许愿者计划驾车来田野许愿,这些许愿者都会像 Mr. P 一样任选一种最优策略行动。Mr. S 认为非左右方向(即上、左上45∘45^{\circ}45∘ 、右上 45∘45^{\circ}45∘ 三个方向)的车辙印很不美观,为了维护田野的形象,他打算租用一些轧路机,在这群许愿者到来之前夯实所有「可能留下非左右方向车辙印」的地面。
「可能留下非左右方向车辙印」的地面应当是田野上的若干条线段,其中每条线段都包含在某一种最优策略的行进路线中。每台轧路机都采取满足以下三个条件的工作模式:
- 从原点或任意一棵树出发。
- 只能向上、左上 45∘45^{\circ}45∘ 、右上 45∘45^{\circ}45∘ 三个方向之一移动,并且只能在树下改变方向或停止。
- 只能经过「可能留下非左右方向车辙印」的地面,但是同一块地面可以被多台轧路机经过。
- 请给 Mr .P 指出任意一条最优路线。
- 请告诉 Mr. S 最少需要租用多少台轧路机。
Input
输入文件的第一行包含一个正整数 nnn,表示许愿树的数量。
接下来 nnn 行,第 i+1i+1i+1 行包含两个整数 xi,yix_i,y_ixi,yi,中间用单个空格隔开,表示第 iii 棵许愿树的坐标。
接下来 nnn 行,第 i+1i+1i+1 行包含两个整数 xi,yix_i,y_ixi,yi,中间用单个空格隔开,表示第 iii 棵许愿树的坐标。
Output
输出文件包括三行。
输出文件的第一行输出一个整数 mmm,表示 Mr. P 最多能在多少棵树下许愿。
输出文件的第二行输出 mmm 个整数,相邻整数之间用单个空格隔开,表示 Mr. P 应该依次在哪些树下许愿。
输出文件的第三行输出一个整数,表示 Mr. S 最少需要租用多少台轧路机。
输出文件的第一行输出一个整数 mmm,表示 Mr. P 最多能在多少棵树下许愿。
输出文件的第二行输出 mmm 个整数,相邻整数之间用单个空格隔开,表示 Mr. P 应该依次在哪些树下许愿。
输出文件的第三行输出一个整数,表示 Mr. S 最少需要租用多少台轧路机。
Sample 1 Input
6
-1 1
1 1
-2 2
0 8
0 9
0 10
Sample 1 Output
3
2 1 3
3