问题 1876 --假日旅游

1876: 假日旅游

时间限制: 1 Sec  内存限制: 128 MB
提交: 9  解决: 4
[提交][状态][讨论版][命题人:]

题目描述

  Merry准备正在假日和好友去当地最大的公园Fanboo Park游玩度过一个愉快假期,已知公园有N个景点,Merry很想游玩每个景点,虽然时间有限,她觉得至少游玩了其中的M个景点才算过瘾。作为Merry好朋友的你,给Merry帮帮忙吧!

给定N 个景点的坐标,请你找出一个最小的矩形,并且这个矩形能够至少覆盖M个点,这个矩形的四个顶点必须是整数,并且它的边必须平行于x-y轴。另外,需要注意的是如果一个点在这个矩形的边上,那么这个点不算被矩形覆盖。

输入

输入的第一行是所有测试数据的组数。每组测试数据的第一行是两个整数N,M(1 ≤ MN ≤ 200)N是景点的个数。接下来的N行包括两个整数 xi, yi (1 ≤ xi, yi ≤10,000),描述的是每个景点的坐标。每组测试数据之前有一个空行。

输出

对于每组数据,请输出这个最小矩形的面积

样例输入

3

2 1
200 6
100 5

2 2
200 6
100 5

2 1
1 1
1 1

样例输出

4
306
4

提示

来源

 

[提交][状态]