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