攻击[JSOI2016]

发表于 分类于 ，

链接

loj

题解

前 $20%$ ：$m=2$，暴力判断。

中间 $20%$：$n=0$，枚举两个点，然后扫描线。

好了，开始搞正解。

发现根本不可做，于是来模拟退火。

退火的能量表示成一个二元组 <点的个数，圆的最大半径>。

要使得点的个数最大，且在点的个数相同时，圆的最大半径最大才行。

然后对于一个点，算这个二元组可以 $O(n+m)$ 算。

那么退火次数可以卡一卡，调一堆参，就过了。

时间复杂度玄学。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int N=1005;
const db eps=1e-7;
#define pid pair<int,db>
struct P{
	db x,y;
	P(db _x=0,db _y=0){x=_x; y=_y;}
};
inline db dis(P A,P B){return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}
struct C{db x,y,r;};
C c[N];
P p[N];

int n,m;
db R;
inline db Rand(db x)
{
	return x*2*((0.0+rand())/RAND_MAX)-x;
}
inline pid calc(int x,int y)
{
	int tot=0; db r=R;
	fo(i,1,n) r=min(r,dis(P(x,y),P(c[i].x,c[i].y))-c[i].r);
	if(r<0) return mp(0,-1);
	fo(i,1,m) if(dis(p[i],P(x,y))<=r) tot++;
	return mp(tot,r);
}
inline int solve(db x,db y)
{
	pid now=calc(x,y),mx=now,nex;
	db nx,ny,W;
	for(db T=R;T>eps;T*=0.99)
	{
		nx=x+Rand(T),ny=y+Rand(T);
		nex=calc(nx,ny);
		if(nex>now) x=nx,y=ny,now=nex;
		else if(exp(R*(nex.fi==now.fi?nex.se-now.se:nex.fi-now.fi)/T)>((0.0+rand())/RAND_MAX)) x=nx,y=ny,now=nex;
		mx=max(mx,nex);
	}
	return mx.fi;
}
int main()
{
	srand(20030403);
	cin>>n>>m>>R;
	fo(i,1,n) cin>>c[i].x>>c[i].y>>c[i].r;
	fo(i,1,m) cin>>p[i].x>>p[i].y;
	int ans=1;
	fo(i,1,min(100000/m,2000)) ans=max(ans,solve(Rand(R),Rand(R)));
	printf("%d",ans);
	return 0;
}