/ SB域 / 题库 /

着色的矩形 ColoringRectangles

着色的矩形 ColoringRectangles

【题目描述】
在平面中给定N个与坐标轴平行的矩形,第i个矩形的左下角坐标是(x1[i],y1[i]),右上角坐标是(x2[i],y2[i])。
你的任务是从中选择K个矩形,使得所选矩形可视面积最大。如果一些矩形有重叠,那么重叠部分只有编号最大的矩形才可视。换句话说,编号大的矩形“盖”在编号小的矩形之上。请你输出选择的K个矩形的编号。如果有多种方法,输出字典序最小的一组。
【输入文件】
第一行两个整数N,K。
第二行N个整数,表示x1[0]..x1[N-1]。
第三行N个整数,表示y1[0]..y1[N-1]。
第四行N个整数,表示x2[0]..x2[N-1]。
第五行N个整数,表示y2[0]..y2[N-1]。
【输出文件】
一行K个非负整数,表示选择的矩形的编号。编号之间用一个空格隔开。
【输入样例】
3 2
1 3 2
1 2 5
5 7 9
3 4 7
【输出样例】
1 2
【样例说明】
选择矩形0,1,面积为6+8=14
选择矩形0,2,面积为6+14=20
选择矩形1,2,面积为8+14=22。
样例说明
【数据规模和约定】
1<=N<=50
-10000<=所有坐标<=10000
对于任意i,x1[i]<x2[i],y1[i]<y2[i]