本来我跑了200次,最后发现跑15次就能过,没卡常也是最优解(
#include<bits/stdc++.h>
using namespace std;
typedef double db;
const db inf=1e9;
const db pi=acos(-1);
struct node{
db x,y,r;
}a[10],k1,k2;
int n,T;
db ans=inf,S;
db dis(int i,int j)
{
return (db)(sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)));
}
db solve()
{
db s=S;
for(int i=1;i<=n;i++) a[i].r=0;
for(int i=1;i<=n;i++)
{
a[i].r=min(fabs(a[i].x-k1.x),fabs(a[i].x-k2.x));
a[i].r=min(a[i].r,min(fabs(a[i].y-k1.y),fabs(a[i].y-k2.y)));
for(int j=1;j<=i-1;j++)
{
db t=dis(i,j)-a[j].r;
if(t<=0) t=0;
a[i].r=min(a[i].r,t);
}
s-=pi*a[i].r*a[i].r;
}
return s;
}
int rd(db ans)
{
db k=ans-(int)ans;
if(k>=0.5) return (int)ans+1;
else return (int)ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
srand(time(0));
T=15;
cin>>n;
cin>>k1.x>>k1.y>>k2.x>>k2.y;
S=fabs(k1.x-k2.x)*fabs(k1.y-k2.y);
for(int i=1;i<=n;i++)
{
cin>>a[i].x>>a[i].y;
}
while(T--)
{
random_shuffle(a+1,a+n+1);//精髓
ans=min(ans,solve());
}
cout<<rd(ans);
return 0;
}