mxqz 模拟退火调参
查看原帖
mxqz 模拟退火调参
302394
dingshengyang楼主2022/12/19 12:29

70pts。

#include <bits/stdc++.h>
#define R register
#define inl inline
#define fastios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define Debug(file) freopen(file".in","r",stdin);freopen(file".out","w",stdout);
#define random_int uniform_int_distribution<int>
#define random_real uniform_real_distribution<double>
#define delta_T 0.99985
using namespace std;
mt19937 maker(20100727); 
int n,m;double maxR; 
int answer,bestans;
struct building{
    double x,y,r;
}a[12];
struct person{
    double x,y;
}b[1005],ans,best;
typedef person point;
inl double dist(R point p1,R point p2){
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
inl double maxr(R double x,R double y){
    double res = maxR;
    for(R int i = 1;i <= n;i ++)res = min(res,dist(point{x,y},point{a[i].x,a[i].y})-a[i].r);
    return res;
}
inl int f(R double x,R double y,R double r){
    int res = 0;
    for(R int i = 1;i <= m;i ++)if(dist(point{x,y},b[i]) <= r)res ++;
    return res;
}
void SA(){
//    puts("done");
    random_int delta(-(1<<30),+(1<<30));
    random_real cen(0,1);
    R double T = 1000;
    while(T >= 1e-10 && (double)clock()/CLOCKS_PER_SEC <= 0.98){
	    R point cpy = ans;
	    ans.x += delta(maker)*T;
	    ans.y += delta(maker)*T;
	    if(maxr(ans.x,ans.y)<0){
	    	T *= delta_T;
	    	continue;
		}
	    int now = f(ans.x,ans.y,maxr(ans.x,ans.y));
	    int delta = now-answer ;
	    if(delta > 0)answer = now;
	    else if(exp(-delta/T)<cen(maker))answer = now;
	    else ans = cpy;
	    T *= delta_T;
	    if(answer > bestans){
	    	bestans = answer;best = ans;
	    }
    }
}
int main() {
    fastios;
    cin >> n >> m >> maxR;double sx,sy;sx = sy = 0;
    for(R int i = 1;i <= n;i ++)cin >> a[i].x >> a[i].y >> a[i].r;
    for(R int i = 1;i <= m;i ++){
    cin >> b[i].x >> b[i].y; 
    sx += b[i].x;
    sy += b[i].y;
    }
    ans = best = {sx/(double)m,sy/(double)m};
    answer = bestans = f(ans.x,ans.y,maxr(ans.x,ans.y));
    #ifdef ONLINE_JUDGE
//    while((double)clock()/CLOCKS_PER_SEC<=0.98){
//    	maker = mt19937(maker());
//    	SA();
//	}
    SA();	
    maker = mt19937(114514);
    SA();
    maker = mt19937(1919810);
    SA();
    #endif
    #ifdef Local
    SA();SA();SA();SA();SA();SA();SA();SA();SA();
    #endif
    cout << bestans << endl; 
    return 0;
}
2022/12/19 12:29
加载中...