此题就是是求费马点，可以用到模拟退火算法
模拟退火的主要思想是一开始现在一个大范围内游走，逐渐减小搜索范围，最后找到解
我的程序是令马尔科夫链为200（即每次循环进行200次探索），初始温度为40（随机走若干个t步），衰减量为1（每次t--），则当温度降为0时，即找到答案
/**//*
ID: lorelei3
TASK: fence3
LANG: C++
*/
#include <fstream>
#include <ctime>
#include <cmath>
using namespace std;
const int dx[] = 
{1,0,-1,0};
const int dy[] = {0,1,0,-1};
const int MAXN = 160;
ifstream fin("fence3.in");
ofstream fout("fence3.out");
double p[MAXN][4];
int n;
void input(){
fin>>n;
for(int i=0; i<n; ++i){
fin>>p[i][0]>>p[i][1]>>p[i][2]>>p[i][3];
p[i][0]*=10; p[i][1]*=10; p[i][2]*=10; p[i][3]*=10;
}
srand(time(NULL));
}
inline int min(int a, int b){
return a<b?a:b;
}
inline int max(int a, int b){
return a>b?a:b;
}
double compute(int x, int y){
double ret=0;
for(int i=0; i<n; ++i){
int x1=p[i][0], y1=p[i][1];
int x2=p[i][2], y2=p[i][3];
if(y1==y2){
int minx=min(x1,x2), maxx=max(x1,x2);
int yy=y1;
if(x>=minx&&x<=maxx)
ret+=abs(yy-y);
else if(x>maxx)
ret += sqrt((y-yy)*(y-yy)+(x-maxx)*(x-maxx));
else
ret += sqrt((y-yy)*(y-yy)+(x-minx)*(x-minx));
}else if(x1==x2){
int miny=min(y1,y2), maxy=max(y1,y2);
int xx=x1;
if(y>=miny&&y<=maxy)
ret+=abs(xx-x);
else if(y>maxy)
ret += sqrt((y-maxy)*(y-maxy)+(x-xx)*(x-xx));
else
ret += sqrt((y-miny)*(y-miny)+(x-xx)*(x-xx));
}
}
return ret;
}
int x,y;
double ans;
void sa(){
x=p[0][0], y=p[0][1];
int t=40, ma=200, LEN=5;
ans = compute(x,y);
while(--t){
for(int i=0; i<ma; ++i){
for(int j=0; j<4; ++j){
int d = rand()%LEN;
int tx = x+dx[j]*d*t;
int ty = y+dy[j]*d*t;
if(tx>=0 && ty>=0 && tx<=1000 && ty<=1000){
double tmp = compute(tx,ty);
if(tmp<ans){
ans=tmp, x=tx, y=ty;
}
}
}
}
}
}
void output(){
fout.setf(ios::fixed,ios::floatfield);
fout.precision(1);
fout<<(double)x/10<<" "<<(double)y/10<<" "<<ans/10<<endl;
}
int main(){
input();
sa();
output();
return 0;
}
posted on 2011-02-09 13:44
小阮 阅读(755)
评论(3) 编辑 收藏 引用 所属分类:
USACO