题意：给你平面上n个点，删除小于等于k(k<=10)个点使得能用一个最小的平行于坐标系的矩阵覆盖所有点 题解：显然，一定是删除“最外面”的点是最优的。 那么对所有点分别以x、y排序，枚举上下左右边界，判断最小面积。
这个思路第一次见，很神奇
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <sstream>
#include <cmath>
#define LL long long
#define mod 1000000007
using namespace std;
const int maxn =
500000 +
5;
const LL INF =
1e18 +
5;
struct Point{
double x,y;
int id;
}p0[maxn],p1[maxn];
bool cmp1(Point p, Point q){
return p.x < q.x;
}
bool cmp2(Point p, Point q){
return p.y < q.y;
}
bool judge(
int i0,
int i1,
int i2,
int i3,
int n,
int k){
LL L0 = p0[i0].x;
LL R0 = p0[n-
1-i1].x;
LL L1 = p1[i2].y;
LL R1 = p1[n-
1-i3].y;
if(L0 > R0 || L1 > R1)
return false;
set<int> del;
for(
int i=
0; i<i0; i++)
del.insert(p0[i].id);
for(
int i=n-i1; i<n; i++)
del.insert(p0[i].id);
for(
int i=
0; i<i2; i++)
del.insert(p1[i].id);
for(
int i=n-i3; i<n; i++)
del.insert(p1[i].id);
if(del.size() <= k)
return true;
return false;
}
int main(){
int n,k;
scanf(
"%d%d",&n,&k);
k = min(n-
1,k);
for(
int i=
0; i<n; i++){
double x1,y1,x2,y2;
scanf(
"%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
p0[i].x = p1[i].x = (x1 + x2) /
2;
p0[i].y = p1[i].y = (y1 + y2) /
2;
p0[i].id = p1[i].id = i;
}
LL ans = INF;
sort(p0,p0+n,cmp1);
sort(p1,p1+n,cmp2);
for(
int i=
0; i<=k; i++){
for(
int j=
0; j<=k; j++){
for(
int p=
0; p<=k; p++){
for(
int q=
0; q<=k; q++){
if(judge(i,j,p,q,n,k)){
double l0 = p0[i].x;
double r0 = p0[n-
1-j].x;
double l1 = p1[p].y;
double r1 = p1[n-
1-q].y;
LL l = (LL)(r0-l0+
0.5);
LL r = (LL)(r1-l1+
0.5);
if(l ==
0) l =
1;
if(r ==
0) r =
1;
ans = min(ans, l*r);
}
}
}
}
}
printf(
"%lld\n",ans);
}
