注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

USACO 5.2 Electric Fences (fence3)  

2009-10-18 09:46:21|  分类: usaco |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
此题是求费马点,需要用到模拟退火算法
模拟退火的主要思想是一开始现在一个大范围内游走,逐渐减小搜索范围,最后找到解(来源于物理中的淬火)
我的程序是令马尔科夫链为200(即每次循环进行200次探索),初始温度为40(随机走若干个t步),衰减量为1(每次t--),则当温度降为0时,即找到答案
#include<iostream>
#include <fstream>
#include<cmath>
using namespace std;
    ofstream fout ("fence3.out");
    ifstream fin ("fence3.in");
    int f[150][4],n,dd[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
double cc(int x,int y){
           double k=0;
           for(int i=0;i<n;i++){
                   int x1=f[i][0],y1=f[i][1],x2=f[i][2],y2=f[i][3],xx=x,yy=y;
                   if(f[i][1]==f[i][3]){
                     x1=f[i][1],y1=f[i][0],x2=f[i][3],y2=f[i][2],xx=y,yy=x;
                   }
                   if(yy>=min(y1,y2)&&yy<=max(y1,y2))
                     k+=abs(xx-x1);
                   else if(yy>max(y1,y2))
                          k+=sqrt((xx-x1)*(xx-x1)+(yy-max(y1,y2))*(yy-max(y1,y2)));
                        else k+=sqrt((xx-x1)*(xx-x1)+(yy-min(y1,y2))*(yy-min(y1,y2)));
           }
           return k;
}
int main(){
    fin>>n;
    for(int i=0;i<n;i++)
      for(int j=0;j<4;j++){
              fin>>f[i][j];
              f[i][j]*=10;
      }
    int x=f[0][0],y=f[0][1];
    srand(time(NULL));
    int t=40,ma=200,pp=5;
    double q=cc(x,y);
    while(--t){
               for(int j=0;j<ma;j++)
                 for(int i=0;i<4;i++){
                       int u=rand()%pp;
                       int x1=x+dd[i][0]*t*u,y1=y+dd[i][1]*t*u;
                       if(x1>=0&&y1>=0&&x1<=1000&&y1<=1000){
                         double qq=cc(x1,y1);
                         if(qq<q){
                                q=qq;
                                x=x1;
                                y=y1;
                         }
                       }
               }
    }
    fout.setf(ios::fixed,ios::floatfield);
    fout.precision(1);
    fout<<(double)x/10<<" "<<(double)y/10<<" "<<q/10<<endl;
    return 0;
}
  评论这张
 
阅读(515)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017