TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1307
  • 题目
  • P1307【NOIP 2002】矩形覆盖
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    在平面上有 n 个点(n <= 50),每个点用一对整数坐标表示。例如:当 n=4 时,4个点的坐标分另为:p1(1,1),p2(2,2),p3(3,6),P4(0,7),见图一。

    这些点可以用 k 个矩形(1<=k<=4)全部覆盖,矩形的边平行于坐标轴。当 k=2 时,可用如图二的两个矩形 sl,s2 覆盖,s1,s2 面积和为 4。问题是当 n 个点坐标和 k 给出后,怎样才能使得覆盖所有点的 k 个矩形的面积之和为最小呢。约定:覆盖一个点的矩形面积为 0;覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开(边线与顶点也都不能重合)。

    输入格式

    n k
    xl y1
    x2 y2
    ... ...
    xn yn (0<=xi,yi<=500)

    输出格式

    一个整数,即满足条件的最小的矩形面积之和。

    样例输入

    4 2
    1 1
    2 2
    3 6
    0 7

    样例输出

    4


    来源  NOIP 2002 T4