数据范围很小，考虑搜索。
我最先想到的是枚举矩形，显然每个矩形的定点必然是输入中给出的点。
然而不仅复杂度不对，还贼难写。
冷静分析一下，不能枚举矩形包括哪个点，可以枚举点属于哪个矩形。
这样每个点有四种情况，复杂度O(n4)，还有check的常数，可以说在TLE的边缘疯狂试探。
实际上，这么多情况是跑不满的，再加一些剪枝，就可以过了。
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<cstdlib> 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<<ans; 89 }