题意:让你求空间内n个点的最小覆盖球。

模拟退火随机走的时候主要有这几种走法:①随机旋转角度。

②直接不随机,往最远的点的方向走,仅仅在尝试接受解的时候用概率。(最小圆/球覆盖时常用)

③往所有点的方向的总和走,仅仅在尝试接受解的时候用概率。(费马点时常用)

像这题,我用第一种最暴力的随机,死活过不了……

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
const double EPS=0.00000001;
const double PI=acos(-1.0);
struct Point{
double x,y,z;
Point(const double &x,const double &y,const double &z){
this->x=x;
this->y=y;
this->z=z;
}
Point(){}
void read(){
scanf("%lf%lf%lf",&x,&y,&z);
}
double length(){
return sqrt(x*x+y*y+z*z);
}
}a[35],p,allp;
double ans,allans;
int n;
typedef Point Vector;
Vector operator - (const Point &a,const Point &b){
return Vector(a.x-b.x,a.y-b.y,a.z-b.z);
}
Vector operator + (const Vector &a,const Vector &b){
return Vector(a.x+b.x,a.y+b.y,a.z+b.z);
}
Vector operator * (const double &K,const Vector &v){
return Vector(K*v.x,K*v.y,K*v.z);
}
double calc(Point p){
double res=0.0;
for(int i=1;i<=n;++i){
res=max(res,(a[i]-p).length());
}
return res;
}
//double ran(){
// int fm=rand()%10000+1;
// return ((rand()&1) ? -1.0 : 1.0)*((double)(rand()%(fm+1))/(double)fm);
//}
Vector unit(Vector v){
double l=v.length();
return Vector(v.x/l,v.y/l,v.z/l);
}
int main(){
srand(233);
//freopen("poj2069.in","r",stdin);
while(1){
scanf("%d",&n);
if(!n){
return 0;
}
allans=100000.0;
for(int i=1;i<=n;++i){
a[i].read();
}
// for(int j=1;j<=n;++j){
p=a[1];
ans=calc(p);
double T=sqrt(20000.0);
while(T>EPS){
double bestnow=100000.0;
Point besttp;
// for(int i=1;i<=30;++i){
// double rad=(double)(rand()%10000+1)/10000.0*2.0*PI;
int to;
double far=0.0;
for(int k=1;k<=n;++k){
double tmp=(a[k]-p).length();
if(tmp>far){
far=tmp;
to=k;
}
}
Point tp=p+T*unit(a[to]-p);
double now=calc(tp);
if(now<bestnow){
bestnow=now;
besttp=tp;
}
// }
if(bestnow-100000.0<-EPS && (bestnow<ans || exp((ans-bestnow)/T)*10000.0>(double)(rand()%10000))){
ans=bestnow;
p=besttp;
}
T*=0.99;
}
if(ans<allans){
allans=ans;
// allp=p;
}
// }
printf("%.5lf\n",fabs(allans));
}
return 0;
}

最新文章

  1. Drop all the tables, stored procedures, triggers, constraints and all the dependencies in one SQL statement
  2. BZOJ 1305: [CQOI2009]dance跳舞 二分+最大流
  3. C++-Qt【4】-CheckBox on QListView
  4. 为ASP.NET MVC视图输出json
  5. git clone简介
  6. HDU 4405:Aeroplane chess(概率DP入门)
  7. selenium+python自动化之xpath定位
  8. POJ 1781
  9. 当rsync遇到非默认端口的ssh
  10. hdoj 1495 非常可乐【bfs隐式图】
  11. iOS_icon命名规范 (iPhone_retina屏幕开发)
  12. 各浏览器Cookie大小、个数限制
  13. Java serialVersionUID
  14. PL/SQL 触发器简介
  15. 九度online judge 1543 二叉树
  16. 一个小玩具:Python调用Mysql
  17. StarTeam SDK 13 下载安装
  18. hdu3570, 超级简单的斜率优化dp
  19. markdown语法小结
  20. Java为什么要配置环境变量及如何配置环境变量

热门文章

  1. 贿赂囚犯 Bribe the prisoners ( 动态规划+剪枝)
  2. HDU 1548 A strange lift (广搜)
  3. MSSQL 数据库性能优化
  4. 设计模式之Builder
  5. Oracle 表连接方式
  6. tornado 响应头 中断 状态码 工作流程
  7. FineReport——插入行策略
  8. redis 的优化
  9. linux命令(42):wc命令
  10. linux命令(40):at命令