题解 P6415 【[COCI2014-2015#1] KLOPKA】
Suuon_Kanderu
2020-04-19 11:35:50
看到大佬们都用了贪心，数论等一切牛的办法，我给大家提供一个：
$ {\colorbox{#52c41A}{\color{#FFF}复杂度过千万，暴力能碾标算}}$
这个题数据很小，枚举，秒切。
首先，我们枚举每个正方形的左上角，复杂度$O(100^2)$
我们枚举每个正方形的边长，复杂度$O(100)$(当然可以有剪枝，不过数据小，不需要)
然后，每次正方形边长扩大时，看看是否包含所有的点。如果是，和 ans 打擂台，取最小值。 复杂度 $O(N)$
总体来说$O(100^3\cdot N = 2 \times10^7)$(才千万级，完全在评测机的掌控之中)
但不知为何，跑得快到47ms。（给评测机点赞）
```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
struct point {
int x,y;
}a[22];
int main() {
int maxx = -100,maxy = -100,ans = 0x7fffffff;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y)
,maxx = max(maxx,a[i].x),maxy = max(maxy,a[i].y);//小剪枝
for(int i = 1; i <= maxx; i++)//枚举正方形左上角
for(int j = 1; j <= maxy; j++){
int f = 0;//这个是看正方形有没有覆盖所有的点
for(int k = 1; k <= 100; k++) {//枚举正方形边长
f = 0;//别忘清零
for(int u = 1; u <= n; u++){
if((a[u].x >= i && a[u].y >= j
&& a[u].x <= i+k-1 && a[u].y <= j+k-1));
else {
f = 1;break; //如果有一个点没被覆盖
}
}
if(f == 0)ans = min(ans,k);//打擂台取最小值
}
}
cout << (ans-1)* (ans-1)<< endl;//然而我们取得是边长+1，所以面积就是这样
return 0;
}
```