首页 > > 程序设计 > C/C++ >

【noip 2002】矩形覆盖

2018-06-17 21:44:26来源：未知阅读 ()

题目描述

在平面上有 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：

输出样例#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 }