#P18305. Just Mining
Just Mining
Just Mining
矮人在深矿的底层发现了一些新的金矿床。把矿井底层看成平面,矿床的位置由点的多重集 给出,第 个矿床的预估价值是 。不同矿床可能具有相同坐标,但它们仍然是可以分别选择的不同矿床。
过度开采某些区域可能导致矿井不稳定甚至坍塌。矿工、地质学家和工程师共同找出了这些危险区域,它们由圆的多重集 描述。第 个圆有容量 ,表示该圆所围成的闭圆盘内,包括圆周上的矿床,最多可以开采 个。
请选出一部分矿床,使它们的价值总和最大,并且不超过任何一个圆的容量。形式化地,令 为位于第 个闭圆盘中的矿床多重集,所选矿床集合 必须满足
保证所有圆可以划分成两个互不相交的族 ,且每个族都满足层叠性质:同一族中,任意两个圆所围成的区域要么彼此分离,要么一个严格包含另一个;同一族中任意两个圆的圆周没有公共点。因此,同一族中不会出现相交、相切或重合的圆周。这里的“圆周没有公共点”不排除圆盘的严格包含。
这个划分并没有在输入中给出。圆的输入是多重集,允许出现相同的圆,只要仍然满足能分成上述两个族的保证。
输入格式
第一行包含两个整数 ,分别表示圆和矿床的数量。
接下来 行,每行包含四个整数 ,分别表示第 个圆的圆心坐标、半径和容量。
接下来 行,每行包含三个整数 ,分别表示第 个矿床的坐标和价值。不同矿床的坐标可以相同。
输入仅有一组数据。
输出格式
输出三行。
第一行输出所选矿床的最大可能价值总和。
第二行输出一个达到该最大价值的方案所选矿床数。
第三行输出这个方案中所有矿床的编号。矿床按照输入顺序从 开始编号。可以以任意顺序输出,每个编号最多出现一次。
如果存在多种最优方案,输出任意一种即可。
数据范围
- ;
- 所有坐标满足 ;
- ;
- 。
保证所有圆可以划分为两个满足上述条件的族。
样例 1
5 5
3 5 2 2
4 10 4 2
5 10 2 3
5 5 5 2
14 4 2 3
6 11 3
3 8 5
4 6 20
9 5 4
14 5 1
28
4
1 3 4 5
样例 2
3 2
4 7 2 2
4 8 1 1
8 7 1 1
4 7 5
4 8 4
5
1
1