数据范围很小,考虑搜索。
我最先想到的是枚举矩形,显然每个矩形的定点必然是输入中给出的点。
然而不仅复杂度不对,还贼难写。
冷静分析一下,不能枚举矩形包括哪个点,可以枚举点属于哪个矩形。
这样每个点有四种情况,复杂度O(n4),还有check的常数,可以说在TLE的边缘疯狂试探。
实际上,这么多情况是跑不满的,再加一些剪枝,就可以过了。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 inline int read(){ 9 int x=0;char ch=getchar();10 while(ch<'0'||ch>'9')ch=getchar();11 while(ch>='0'&&ch<='9'){12 x=x*10+ch-'0';ch=getchar();13 }14 return x;15 }16 17 const int N=55;18 19 struct poi{20 int x,y;21 }p[N];22 23 struct mtrx{24 int l,r,u,d;25 bool fl;26 }m[5];27 28 29 int n,k;30 31 int ans=1e9+7;32 33 inline bool ins(int a,int x,int y){34 if(x<=m[a].r&&x>=m[a].l&&y<=m[a].u&&y>=m[a].d)return true;35 return false;36 }//判断(x,y)是否在a矩形中 37 38 inline bool check(int a,int b){39 if(ins(a,m[b].l,m[b].u))return true;40 if(ins(a,m[b].l,m[b].d))return true;41 if(ins(a,m[b].r,m[b].u))return true;42 if(ins(a,m[b].r,m[b].d))return true;43 return false;44 }//判断a,b矩形是否相交 45 46 inline void dfs(int now){47 int val=0;48 for(int i=1;i<=k;++i){49 if(m[i].fl){50 for(int j=i+1;j<=k;++j){51 if(m[j].fl&&check(i,j))return ;//如果和另一个矩形相交 52 }53 }54 val+=(m[i].r-m[i].l)*(m[i].u-m[i].d);55 }//先求一波当下的答案 56 if(val>ans)return;57 if(now==n+1){58 ans=min(ans,val);59 return;60 }61 for(int i=1;i<=k;++i){62 mtrx shep=m[i];//用于恢复状态 63 if(!m[i].fl){ 64 m[i].l=m[i].r=p[now].x;65 m[i].u=m[i].d=p[now].y;66 m[i].fl=1;67 dfs(now+1);68 m[i]=shep;69 break;70 }//这里break是因为,放到空矩形肯定比其他矩形不劣。 71 else{72 m[i].l=min(m[i].l,p[now].x);73 m[i].r=max(m[i].r,p[now].x);74 m[i].d=min(m[i].d,p[now].y);75 m[i].u=max(m[i].u,p[now].y);76 dfs(now+1);77 m[i]=shep;78 }79 }80 }81 82 int main(){83 n=read();k=read();84 for(int i=1;i<=n;++i){85 p[i].x=read();p[i].y=read();86 }87 dfs(1);88 cout<