1 #include <iostream>
2 #include <algorithm>
3 #include <vector>
4
5 using namespace std;
6 struct Node
7 {
8 int xi,yi;
9 Node(int x=0,int y=0):xi(x),yi(y){};
10 };
11 bool op1(const Node& a,const Node& b)
12 {
13 if(a.xi==b.xi)return a.yi<b.yi;
14 return a.xi<b.xi;
15 }
16 bool op2(const Node& a,const Node& b)
17 {
18 if(a.yi==b.yi)return a.xi<b.xi;
19 return a.yi<b.yi;
20 };
21
22 int marx[10005];
23
24 vector<Node> vecx,vecy;
25 int main()
26 {
27 int c;
28 scanf("%d",&c);
29 while(c--){
30 vecx.clear();
31 vecy.clear();
32 int n,m;
33 scanf("%d%d",&n,&m);
34 int x,y;
35 for(int i=0;i<n;i++){
36 scanf("%d%d",&x,&y);
37 Node tmp(x,y);
38 ++marx[x];
39 vecx.push_back(tmp);
40 vecy.push_back(tmp);
41 }
42
43 sort(vecx.begin(),vecx.end(),op1);
44 sort(vecy.begin(),vecy.end(),op2);
45
46 int ans=0x7fffffff;
47 int start=0,cnt,tt,end=0;
48 for(int i=0;i<n;++i){
49 for(int j=i;j<n;++j){
50 start=0;
51 end=-1;
52 cnt=0;
53 tt=0;
54 for(start=0;start<n&&end<n;){
55 if(cnt<m){
56 end++;
57 if(end==n)break;
58 if(vecx[end].yi<=vecy[j].yi&&vecx[end].yi>=vecy[i].yi)cnt++;
59 }
60 else{
61 if(vecx[start].yi<=vecy[j].yi&&vecx[start].yi>=vecy[i].yi){
62 int lenx=abs(vecx[end].xi-vecx[start].xi)+2;
63 int leny=abs(vecy[i].yi-vecy[j].yi)+2;
64 if(lenx*leny<ans)ans=lenx*leny;
65 }
66 if(vecx[start].yi<=vecy[j].yi&&vecx[start].yi>=vecy[i].yi)cnt--;
67 start++;
68 }
69 }
70 }
71 }
72 printf("%d\n",ans); //start++
73 }
74 return 0;
75 }
實力不夠...繼續努力...
posted on 2008-07-28 17:43
小果子 閱讀(256)
評論(0) 編輯 收藏 引用 所屬分類:
Acm