退火一直输出0求调
查看原帖
退火一直输出0求调
130819
Hayzeros楼主2022/11/16 15:36
#include<cstdio>
#include<cmath>
#include<stdlib.h>
#include<time.h>
using namespace std;
int n,m,jx[11],jy[11],mx[1010],my[1010],jr[11],R,zx,zy;
double ds(double x1,double y1,double x2,double y2)
{return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
int js(double tx,double ty)
{
    double rin=R; int sum=0;
    for (int i=1; i<=n; i++) {double k=ds(tx,ty,jx[i],jy[i])-jr[i]; rin=k<rin? k:rin;}
    for (int i=1; i<=m; i++) if (rin+1e-4>=ds(tx,ty,mx[i],my[i])) sum++;
    return sum;
}
int sa()
{
    double t=5000,x1,y1; int ans;
    x1=zx; y1=zy;
    ans=js(x1,y1);
    while (t>=1e-10)
    {
        t*=0.996;
        double X=x1+((rand()<<1)-RAND_MAX)*t,Y=y1+((rand()<<1)-RAND_MAX)*t;
        int sum=js(X,Y);
        int del=sum-ans;
        if (del>0)
        {
            ans=sum; x1=X; y1=Y;
        }
        else if (exp(del/t)*RAND_MAX>rand()) x1=X,y1=Y;
    }
    return ans;
}
int main()
{
    srand(time(0));
    scanf("%d%d%d",&n,&m,&R);
    for (int i=1; i<=n; i++) scanf("%d",jx+i),scanf("%d",jy+i),scanf("%d",jr+i);
    for (int i=1; i<=m; i++) scanf("%d",mx+i),scanf("%d",my+i),zx+=mx[i],zy+=my[i];
    zx/=m; zy/=m;
    int ans=0;
    while ((double)clock()/CLOCKS_PER_SEC<=0.95) {int k=sa(); ans=k>ans? k:ans;}
    printf("%d",ans);
    return 0;
}

2022/11/16 15:36
加载中...