xiaoguozi's Blog
Pay it forword - 我并不觉的自豪,我所尝试的事情都失败了······习惯原本生活的人不容易改变,就算现状很糟,他们也很难改变,在过程中,他们还是放弃了······他们一放弃,大家就都是输家······让爱传出去,很困难,也无法预料,人们需要更细心的观察别人,要随时注意才能保护别人,因为他们未必知道自己要什么·····
 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 小果子 阅读(247) 评论(0)  编辑 收藏 引用 所属分类: Acm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理