本道题可以理解成一个平面直角坐标系,在坐标系上标出整个矩形和油滴的坐标,计算两个油滴的面积和直径,判断点是否在圆内(点与圆的位置关系),利用使用坐标求两点间距离的公式取解。
代码如下:
#include<bits/stdc++.h>
using namespace std;
#define PI 3.1415926
const int N=8;
int n,xa,xb,ya,yb;
struct node{
int x,y;
double r;
}nod[N];
double ma=0;
int vis[N];
double cal(int i){
double r1=min(abs(nod[i].x-xa),abs(nod[i].x-xb));
double r2=min(abs(nod[i].y-ya),abs(nod[i].y-yb));
double r=min(r1,r2);
for(int j=1;j<=n;j++){
if(i!=j&&vis[j]){
double d=sqrt(pow(nod[i].x-nod[j].x,2)+pow(nod[i].y-nod[j].y,2));
double dis=d-nod[j].r;
if(dis<=0) r=0.0;
else r=min(r,dis);
}
}
return r;
}
void dfs(int k,double sum){
if(k==n+1){
ma=max(ma,sum);
return;
}
for(int i=1;i<=n;i++){
if(vis[i]) continue;
vis[i]=1;
nod[i].r=cal(i);
dfs(k+1,sum+PI*pow(nod[i].r,2));
vis[i]=0;
}
}
int main(){
scanf("%d",&n);
scanf("%d %d %d %d",&xa,&ya,&xb,&yb);
for(int i=1;i<=n;i++){
scanf("%d %d",&nod[i].x,&nod[i].y);
}
dfs(1,0);
double s=abs(xa-xb)*abs(ya-yb);
int res=round(s-ma);
printf("%d\n",res);
return 0;
}