#include<cstdio>
#include<iostream>
#include<math.h>
#include<algorithm>
#define M 200
#define INT 100000000
using namespace std;
struct cood
{
int x;
int y;
cood(int x1=0,int y1=0):x(x1),y(y1){};
};
int cmp1(cood x,cood y)
{
if(x.x<y.x)return 1;
else return 0;
}
int cmp2(cood x,cood y)
{
if(x.y<y.y)return -1;
else return 0;
}
cood c1[M];
cood c2[M];
int main()
{
int cs;
scanf("%d",&cs);
while(cs--)
{
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%d%d",&c1[i].x,&c1[i].y);
c2[i].x=c1[i].x;
c2[i].y=c1[i].y;
}
sort(c1,c1+n,cmp1);
sort(c2,c2+n,cmp2);
double area=INT;
for(int i=0;i<n-m+1;i++)
{
for(int j=i+m-1;j<n;j++)
{
int count=0;
int top=0;
for(int k=0;k<n-m+1;)
{
if((c2[k].x<=c1[j].x&&c2[k].x>=c1[i].x));else {k++;continue;}
while(top<n)
{
if(c2[top].x<=c1[j].x&&c2[top].x>=c1[i].x)count++;
top++;
if(count>=m)break;
}
if(count>=m)
{
double h=abs(c2[top-1].y-c2[k].y)+2;
double w=abs(c1[j].x-c1[i].x)+2;
if(area>h*w)area=h*w;
count--;
k++;
}
if(top==n)break;
}
}
}
printf("%.0f\n",area);
}
}
这是我写的。。有什么不好的地方请指导！！
这题的离散化搜索还真值得学习啊....