https://www.luogu.org/problemnew/show/P4703
题意：给出平面上的n个圆，求没有被覆盖的点坐标。不存在输出GG。
此题的解空间比较平滑，使用爬山无大碍
但是要注意新随机出来的点坐标范围，不能太大也不能太小
1.爬山 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
using namespace std;
const double r=0.8;
double R,RR;
double xx,yy;
struct node {
double x,y;
} a[15];
int n,l;
inline double Ran(double x) {
return rand()%10001/10000.0*x;
}
inline int calc(double xx,double yy) {
int cnt=0;
for (int i=1;i<=n;i++) {
if ((a[i].x-xx)*(a[i].x-xx)+(a[i].y-yy)*(a[i].y-yy)<R*R+1e-6) cnt++;
}
return cnt;
}
inline void getnew(double &nx,double &ny) {
double tmp=max((double)l,RR);
do {
nx=xx+Ran(2*tmp)-tmp;
} while (nx<0||nx>l);
do {
ny=yy+Ran(2*tmp)-tmp;
} while (ny<0||ny>l);
RR*=r;
}
void ps() {
xx=Ran(l),yy=Ran(l);
for (int i=1;i<=1e3;i++) {
if (calc(xx,yy)==0) return;
double nx,ny;
getnew(nx,ny);
double dE=calc(nx,ny)-calc(xx,yy);
if (dE<=0) xx=nx,yy=ny;
}
}
int main() {
scanf("%d%d",&n,&l);R=(double)l/n;RR=l;
for (int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
srand(time(0));
for (int i=1;i<=100;i++) {
ps();
if (calc(xx,yy)==0) {
printf("%lf %lf",xx,yy);
return 0;
}
}
printf("GG");
return 0;
}
2.退火
此题接受劣解概率较小，注意调参 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
using namespace std;
const double T_min=1e-8;
const double r=0.98;
double T=1,R,RR;
double xx,yy;
struct node {
double x,y;
} a[15];
int n,l;
inline double Ran(double x) {
return rand()%10001/10000.0*x;
}
inline int calc(double xx,double yy) {
int cnt=0;
for (int i=1;i<=n;i++) {
if ((a[i].x-xx)*(a[i].x-xx)+(a[i].y-yy)*(a[i].y-yy)<R*R+1e-6) cnt++;
}
return cnt;
}
inline void getnew(double &nx,double &ny) {
double tmp=max((double)l,RR);
do {
nx=xx+Ran(2*tmp)-tmp;
} while (nx<0||nx>l);
do {
ny=yy+Ran(2*tmp)-tmp;
} while (ny<0||ny>l);
RR*=r;
}
void mnth() {
xx=Ran(l),yy=Ran(l);
while (T>T_min) {
if (calc(xx,yy)==0) return;
double nx,ny;
getnew(nx,ny);
double dE=calc(nx,ny)-calc(xx,yy);
if (dE<=0) xx=nx,yy=ny;
else if (exp(-dE/T)>Ran(1)) xx=nx,yy=ny;
T=r*T;
}
}
int main() {
scanf("%d%d",&n,&l);R=(double)l/n;RR=l;
for (int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
srand(time(0));
mnth();
if (calc(xx,yy)==0) printf("%lf %lf",xx,yy);
else printf("GG");
return 0;
}