分享一个随机化做法(逃
查看原帖
分享一个随机化做法(逃
913522
luobo215楼主2023/10/31 10:09

本来我跑了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;
}
2023/10/31 10:09
加载中...