题意：
平面上有n个点，现在要求一个面积最小的矩形能完全覆盖其中的m个点（边界不算）。
分析：
求满足某个性质的最小区间的问题尺取法比二分还要高效，这题可以在x上暴力枚举，，在y上用尺取法（在x,y上都用尺取法是不对的）。
代码：
//poj 3681//sep9#include <iostream>#include <algorithm>using namespace std;int n,m,ans;struct P{int x,y;}pnt1[256],pnt2[256];int cmp1(P a,P b){return a.x<b.x;}int cmp2(P a,P b){return a.y<b.y;}int vis[256];void judge(int lx,int rx){int y[256],u=0,d=0;for(int i=0;i<n;++i)if(pnt2[i].x>=lx&&pnt2[i].x<=rx){y[u++]=pnt2[i].y;if(u-d==m){ans=min(ans,(y[u-1]-y[d]+2)*(rx-lx+2));++d;}}}int main(){int cases;scanf("%d",&cases);while(cases–){scanf("%d%d",&n,&m);for(int i=0;i<n;++i){scanf("%d%d",&pnt1[i].x,&pnt1[i].y);pnt2[i]=pnt1[i];}sort(pnt1,pnt1+n,cmp1);sort(pnt2,pnt2+n,cmp2);ans=INT_MAX;int l,r;for(int i=0;i<n;++i)for(int j=i;j<n;++j)judge(pnt1[i].x,pnt1[j].x);printf("%d\n",ans);}return 0;}
不要气馁于那前方的阴影，那只是因为我背后光芒万丈
