USACO 5.2.2 Electric Fences
中文题意
这题首先是精读要求不高,只需要输出1位小数,然后范围不大,坐标是0-100.线段条数是150.我一开始想暴力搞,可是死在第7组上.死活过不了.然后去学校的群里问,热心人很多,不过没解决问题.在这里还是要感谢下他们的.然后去各大群里问,最囧的是很多人把线段看成直线,然后说”X和Y分开搞,然后不是显然么”,知道是线段后就说出了各种自己的方法,一开始我问了czw.他说可以模拟退火搞,那个时候我不知道模拟退火的一些细节,就没去试.后来在DIY群里,各大神牛说这数据,模拟退火肯定可搞.就试着去搞了下,发现模拟退火还是比较好写的,不过我总想着它不靠谱,总觉得可能不对,总想着会在中间某一步进入死胡同…..不过看了一些论文之后才有那么一点点感觉,反正是个RP问题[我还是顽固的这么认为],那么就拼拼RP吧.下面是官方的题解.也是模拟退火,不过个人觉得这个还是比较靠谱的.具体的模拟退火还是自己搜吧,大致过程就是不断的在当前最优点的领域节点中找一个最优点
/
/
#include
#include
#define FMAX 135
#define MOVES 50
#define IMAX 4
int numfence
FILE int,out
struct fence
double totaldist(double ,double);
void swap(int ,int &);
struct fence
{
int minx,maxx,miny,maxy
void setvals()
{
fscanf(in,“%d%d%d%d”,minx,&miny,&maxx,&maxy);
if(minx>maxx)
swap(minx,maxx);
if(miny>maxy)
swap(miny,maxy);
}
}feces[FMAX];
double totaldist(double x,double y)
{
int a
double ans=0,xdiff,ydiff
for(a=0a<numfence;a++)
{
if(fences[a].minx > x)
xdiff=fences[a].minx-x
else
{
if(fences[a].maxx<x)
xdiff=x-fences[a].maxx
else
xdiff=0
}
if(fences[a].miny>y)
ydiff=fences[a].miny-y
else
{
if(fences[a].maxy<y)
ydiff=y-fences[a].maxy
else
ydiff=0
}
answer += sqrt(xdiffxdiff + ydiffydiff);
}
return answer
}
void swap(int a,int &b)
{
int tmp=a
a=b;
b=tmp
}
int main(void)
{
in=fopen(“fence3.in”,“r”);
out=fopen(“fence3.out”,“w”);
int a,b,c,best
double elecx,elecy,xchange,ychange,tsum
double bestsum=100000.0
double xinc[IMAX],yinc[IMAx],pi
pi=acos(-1.0);
for(a=0a < IMAX;a++)
{
xinc[a]=cos(2pia/IMAX);
yinc[a]=sin(2pia/IMAX);
}
fscanf(in,“%d”,numfence);
for(a=0a<numfence;a++)
fences[a].setvals();
elecx=0
elecy=0
xchange=20
ychange=20
bestsum=totaldist(elecx,elecy);
for(b=1b<=MOVES;b++)
{
if(0==b%10)
{
ychange=ychange0.1
xchange=xchange0.1
}
best=-1
for(c=0c<IMAX;c++)
{
elecx += xchangexinc[c];
elecy += xchangeyinc[c];
tsum=totaldist(elecx,elecy);
if(tsum<bestsum)
{
bestsum=tsum
best=c
}
elecx -= xchangexinc[c];
elecy -= ychangeyinc[c];
}
if(-1 != best)
{
elecx += xchangexinc[best];
elecy += ychangeyinc[best];
}
bestsum=totaldist(elecx,elecy);
}
fprintf(out,“%.1f %.1f %.1f\n“,elecx,elecy,bestsum);
return 0
}
/
#include
#include
#define FMAX 135
#define MOVES 50
#define IMAX 4
int numfence
FILE int,out
struct fence
double totaldist(double ,double);
void swap(int ,int &);
struct fence
{
int minx,maxx,miny,maxy
void setvals()
{
fscanf(in,“%d%d%d%d”,minx,&miny,&maxx,&maxy);
if(minx>maxx)
swap(minx,maxx);
if(miny>maxy)
swap(miny,maxy);
}
}feces[FMAX];
double totaldist(double x,double y)
{
int a
double ans=0,xdiff,ydiff
for(a=0a<numfence;a++)
{
if(fences[a].minx > x)
xdiff=fences[a].minx-x
else
{
if(fences[a].maxx<x)
xdiff=x-fences[a].maxx
else
xdiff=0
}
if(fences[a].miny>y)
ydiff=fences[a].miny-y
else
{
if(fences[a].maxy<y)
ydiff=y-fences[a].maxy
else
ydiff=0
}
answer += sqrt(xdiffxdiff + ydiffydiff);
}
return answer
}
void swap(int a,int &b)
{
int tmp=a
a=b;
b=tmp
}
int main(void)
{
in=fopen(“fence3.in”,“r”);
out=fopen(“fence3.out”,“w”);
int a,b,c,best
double elecx,elecy,xchange,ychange,tsum
double bestsum=100000.0
double xinc[IMAX],yinc[IMAx],pi
pi=acos(-1.0);
for(a=0a < IMAX;a++)
{
xinc[a]=cos(2pia/IMAX);
yinc[a]=sin(2pia/IMAX);
}
fscanf(in,“%d”,numfence);
for(a=0a<numfence;a++)
fences[a].setvals();
elecx=0
elecy=0
xchange=20
ychange=20
bestsum=totaldist(elecx,elecy);
for(b=1b<=MOVES;b++)
{
if(0==b%10)
{
ychange=ychange0.1
xchange=xchange0.1
}
best=-1
for(c=0c<IMAX;c++)
{
elecx += xchangexinc[c];
elecy += xchangeyinc[c];
tsum=totaldist(elecx,elecy);
if(tsum<bestsum)
{
bestsum=tsum
best=c
}
elecx -= xchangexinc[c];
elecy -= ychangeyinc[c];
}
if(-1 != best)
{
elecx += xchangexinc[best];
elecy += ychangeyinc[best];
}
bestsum=totaldist(elecx,elecy);
}
fprintf(out,“%.1f %.1f %.1f\n“,elecx,elecy,bestsum);
return 0
}
