鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > c++ > >

【noip 2002】矩形覆盖

来源:互联网 作者:佚名 时间:2018-02-27 09:52
题目描述 在平面上有 n 个点(n = 50),每个点用一对整数坐标表示。例如:当 n=4 时,4个点的坐标分另为:p1(1,1),p2(2,2),p3(3,6),P4(0,7),见图一。 这些点可以用 k 个矩形(1=k=4)全部覆盖,矩形的边平行于坐标轴。当 k=2 时,可用如图

题目描述

在平面上有 n 个点(n <= 50),每个点用一对整数坐标表示。例如:当 n=4 时,4个点的坐标分另为:p1(1,1),p2(2,2),p3(3,6),P4(0,7),见图一。

这些点可以用 k 个矩形(1<=k<=4)全部覆盖,矩形的边平行于坐标轴。当 k=2 时,可用如图二的两个矩形 sl,s2 覆盖,s1,s2 面积和为 4。问题是当 n 个点坐标和 k 给出后,怎样才能使得覆盖所有点的 k 个矩形的面积之和为最小呢。约定:覆盖一个点的矩形面积为 0;覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开(边线与顶点也都不能重合)。

输入输出格式

输入格式:

n k xl y1 x2 y2 ... ...

xn yn (0<=xi,yi<=500)

输出格式:

输出至屏幕。格式为:

一个整数,即满足条件的最小的矩形面积之和。

输入输出样例

输入样例#1:
4 2
1 1
2 2
3 6
0 7
输出样例#1:
4
数据略水,其他做法...(你懂得),还是搜索稳。
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 int read(){
 7     int x=0,f=1;char ch=getchar();
 8     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 9     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
10     return x*f;
11 }
12 int n,m,ans=0x3f3f3f3f;
13 struct data1{
14     int x,y;
15 }d1[55];
16 struct data2{
17     int l,r,u,d;
18     bool flag;
19 }d2[5];
20 bool in(data2 a,int xx,int yy){
21     if(a.l<=xx&&xx<=a.r&&a.d<=yy&&yy<=a.u) return true;
22     return false;
23 }
24 bool is_in(data2 a,data2 b){
25     if(in(b,a.l,a.d)||in(b,a.l,a.u)||in(b,a.r,a.d)||in(b,a.r,a.u))
26         return true;
27     return false;
28 }
29 void dfs(int k){
30     int s=0;
31     data2 tmp;
32     for(int i=1;i<=m;i++)
33         if(d2[i].flag){
34             s+=(d2[i].r-d2[i].l)*(d2[i].u-d2[i].d);
35             for(int j=i+1;j<=m;j++)
36                 if(d2[j].flag&&is_in(d2[i],d2[j]))return;
37         }
38     if(s>=ans)return;
39     if(k>n){ans=s;return;}
40     for(int i=1;i<=m;i++){
41         tmp=d2[i];
42         if(!d2[i].flag){
43             d2[i].l=d1[k].x;d2[i].r=d1[k].x;
44             d2[i].u=d1[k].y;d2[i].d=d1[k].y;
45             d2[i].flag=1;
46         }
47         else{
48             d2[i].l=min(d2[i].l,d1[k].x);d2[i].r=max(d2[i].r,d1[k].x);
49             d2[i].d=min(d2[i].d,d1[k].y);d2[i].u=max(d2[i].u,d1[k].y);
50         }
51         dfs(k+1);
52         d2[i]=tmp;
53     }
54 }
55 int main(){
56     n=read(),m=read();
57     for(int i=1;i<=n;i++)d1[i].x=read(),d1[i].y=read();
58     dfs(1);
59     printf("%d",ans);
60     return 0;
61 }
网友评论
<