| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 5632 | Accepted: 1729 |
Description
Input
Output
Sample Input
3 1000 50 1 10 10 100 100 4 10 10 10 90 90 10 90 90 3000 3000 4 1200 85 63 2500 2700 2650 2990 100
Sample Output
The safest point is (1000.0, 50.0). The safest point is (50.0, 50.0). The safest point is (1433.0, 1669.8).
Source
题解：
昨天在网上浏览博客，无意看见有个ACMer交了这题并注明模拟淬火算法，由于在人工智能课上老师提到过这类演化算法-模拟淬火算法。感慨ACM在线OJ还能用模拟淬火算法这类概率算法，于是眼前一亮，有登上好久没有刷题的POJ了，看了道题。
题意是要求到给定n个点的最小距离最大的点，且点限定在给定矩形内。要是一维的，直接三分找极值即可；在平面上就不太好处理了。且这样的点可能不只一个，到底取谁都要考虑。前人提供了模拟淬火算法，直接搞定了。大致步骤如下：
1、随机选取一个合适的控制条件T作为开始
2、随机选取P个起始点，作为可行解
3、分别依据内能更新这P个可行解
4、减小控制条件T，直到终止条件
下面是代码：
#include<iostream>
#include<cmath>
#include<ctime>
#include<cstdio>
using namespace std;
const int MAXN=1000+100;
const int KMEAN=30;
const double INF=1<<30;
const double eps=1e-8;
const double PI=3.141592653;
int x,y,n;
struct Point
{
double x,y;
}myPoint[MAXN],myK[KMEAN];
double dis[KMEAN];
double GetMinDis(double tx,double ty)
{
double minDis=INF,temp;
for(int i=0;i<n;i++)
{
temp=sqrt((tx-myPoint[i].x)*(tx-myPoint[i].x)+(ty-myPoint[i].y)*(ty-myPoint[i].y));
if(temp<minDis)
minDis=temp;
}
return minDis;
}
int main()
{
int cas,i,j;
double temp;
scanf("%d",&cas);
while(cas--)
{
scanf("%d%d%d",&x,&y,&n);
srand((unsigned)time(NULL));
for(i=0;i<n;i++)
scanf("%lf%lf",&myPoint[i].x,&myPoint[i].y);
for(i=0;i<KMEAN;i++)
{
dis[i]=INF;
myK[i].x=rand()%10001/10000.0*x;
myK[i].y=rand()%10001/10000.0*y;
}
for(i=0;i<KMEAN;i++)
dis[i]=GetMinDis(myK[i].x,myK[i].y);
double theta,delta=1.0*(x>y?x:y)/sqrt(1.0*n);
while(delta>eps)
{
for(i=0;i<KMEAN;i++)
{
double nx=myK[i].x,ny=myK[i].y;
for(j=0;j<KMEAN;j++)
{
double tx,ty;
theta=double(rand()%10001)/10000.0*2*PI;
tx=nx+delta*cos(theta);
ty=ny+delta*sin(theta);
if(tx<0||tx>x||ty<0||ty>y)
continue;
temp=GetMinDis(tx,ty);
if(temp>dis[i])
{
myK[i].x=tx;
myK[i].y=ty;
dis[i]=temp;
}
}
}
delta=0.8*delta;
}
int id=-1;
temp=-INF;
for(i=0;i<KMEAN;i++)
{
if(dis[i]>temp)
{
temp=dis[i];
id=i;
}
}
printf("The safest point is (%.1lf, %.1lf).\n",myK[id].x,myK[id].y);
}
return 0;
}
下面是相似的题
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 3274 | Accepted: 1666 |
Description
Input
Output
Sample Input
4 0 0 0 10000 10000 10000 10000 0
Sample Output
28284
题解：
本题与上面那题的唯一区别就是目的函数不同，此处为最短距离和，上面为最短距离的最大者，模拟淬火算法。直接贴代码的。
#include<iostream>
#include<cmath>
#include<ctime>
#include<cstdio>
using namespace std;
const int MAXN=100+10;
const int KMEAN=30;
const double INF=1<<30;
const double eps=1e-8;
const double PI=3.141592653;
double x=10000.0,y=10000.0;
int n;
struct Point
{
double x,y;
}myPoint[MAXN],myK[KMEAN];
double dis[KMEAN];
double GetMinDis(double tx,double ty)
{
double temp=0;
for(int i=0;i<n;i++)
{
temp+=sqrt((tx-myPoint[i].x)*(tx-myPoint[i].x)+(ty-myPoint[i].y)*(ty-myPoint[i].y));
}
return temp;
}
int main()
{
int i,j;
double temp;
while(scanf("%d",&n)!=EOF)
{
srand((unsigned)time(NULL));
for(i=0;i<n;i++)
scanf("%lf%lf",&myPoint[i].x,&myPoint[i].y);
for(i=0;i<KMEAN;i++)
{
dis[i]=INF;
myK[i].x=rand()%10001/10000.0*x;
myK[i].y=rand()%10001/10000.0*y;
}
for(i=0;i<KMEAN;i++)
dis[i]=GetMinDis(myK[i].x,myK[i].y);
double theta,delta=10000.0/sqrt(1.0*n);
while(delta>eps)
{
for(i=0;i<KMEAN;i++)
{
double nx=myK[i].x,ny=myK[i].y;
for(j=0;j<KMEAN;j++)
{
double tx,ty;
theta=double(rand()%10001)/10000.0*2*PI;
tx=nx+delta*cos(theta);//可改变方向
ty=ny+delta*sin(theta);
temp=GetMinDis(tx,ty);
if(temp<dis[i])
{
myK[i].x=tx;
myK[i].y=ty;
dis[i]=temp;
}
}
}
delta=0.98*delta;
}
temp=INF;
for(i=0;i<KMEAN;i++)
{
if(dis[i]<temp)
{
temp=dis[i];
}
}
printf("%.0lf\n",temp);
}
return 0;
}
下面这题是求最小圆覆盖。
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1397 Accepted Submission(s): 625
1000 50 1 10 10 1000 50 4 0 0 1 0 0 1 1 1
(10.0,10.0). 0.0 (0.5,0.5). 0.7
题解：
题意是要求到给定n个点的最大距离最小的点，且点限定在给定矩形内，对应数学模型最小点覆盖。贴段代码：
#include<iostream>
#include<cmath>
#include<ctime>
#include<cstdio>
using namespace std;
const int MAXN=1000+100;
const int KMEAN=30;
const double INF=1<<30;
const double eps=1e-8;
const double PI=3.141592653;
int x,y,n;
struct Point
{
double x,y;
}myPoint[MAXN],myK[KMEAN];
double dis[KMEAN];
double GetMaxDis(double tx,double ty)
{
double maxDis=-INF,temp;
for(int i=0;i<n;i++)
{
temp=sqrt((tx-myPoint[i].x)*(tx-myPoint[i].x)+(ty-myPoint[i].y)*(ty-myPoint[i].y));
if(temp>maxDis)
maxDis=temp;
}
return maxDis;
}
int main()
{
int i,j;
double temp;
while(scanf("%d%d%d",&x,&y,&n)!=EOF)
{
srand((unsigned)time(NULL));
for(i=0;i<n;i++)
scanf("%lf%lf",&myPoint[i].x,&myPoint[i].y);
for(i=0;i<KMEAN;i++)
{
dis[i]=INF;
myK[i].x=rand()%10001/10000.0*x;
myK[i].y=rand()%10001/10000.0*y;
}
for(i=0;i<KMEAN;i++)
dis[i]=GetMaxDis(myK[i].x,myK[i].y);
double theta,delta=1.0*(x>y?x:y)/sqrt(1.0*n);
while(delta>eps)
{
for(i=0;i<KMEAN;i++)
{
double nx=myK[i].x,ny=myK[i].y;
for(j=0;j<KMEAN;j++)
{
double tx,ty;
theta=double(rand()%10001)/10000.0*2*PI;
tx=nx+delta*cos(theta);
ty=ny+delta*sin(theta);
if(tx<0||tx>x||ty<0||ty>y)
continue;
temp=GetMaxDis(tx,ty);
if(temp<dis[i])
{
myK[i].x=tx;
myK[i].y=ty;
dis[i]=temp;
}
}
}
delta=0.8*delta;
}
int id=-1;
temp=INF;
for(i=0;i<KMEAN;i++)
{
if(dis[i]<temp)
{
temp=dis[i];
id=i;
}
}
printf("(%.1lf,%.1lf).\n%.1lf\n",myK[id].x,myK[id].y,temp);
}
return 0;
}
poj1379+POJ2420+hdu3932(最短距离+费马点+模拟淬火算法),布布扣,bubuko.com
poj1379+POJ2420+hdu3932(最短距离+费马点+模拟淬火算法)
原文：http://blog.csdn.net/xiaofengcanyuexj/article/details/25613469