F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 3680 >> 无限RE求助。。
spacetime @ 2017-02-08 12:12:21
[ Quote ] [ Edit ] [ Delete ] 1#
/*退火无限RE是什么鬼。。
我知道可以直接爬山,但想练练退火,结果无限RE。。
代码如下(风格日狗不喜勿喷):*/
#pragma GCC optimize(2)
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#define REP(i,low,high) for(register int i=(low);i<=(high);++i)
#define eps (1e-3)
using namespace std;
typedef long double LD;
struct POINT
{
LD x,y;
void*input() {return cin>>x>>y;}
void*output()const
{
return cout<<setiosflags(ios::fixed)
<<setprecision(3)<<x<<' '<<setprecision(3)<<y<<endl;
}
POINT(const LD&_x=0,const LD&_y=0):x(_x),y(_y) {}
POINT&operator=(const POINT&thr) {return x=thr.x,y=thr.y,*this;}
POINT&operator+=(const POINT&thr) {return x+=thr.x,y+=thr.y,*this;}
template<typename T> POINT operator*(const T&thr)const
{
POINT ret(*this); return ret.x*=thr,ret.y*=thr,ret;
}
template<typename T> POINT&operator/=(const T&thr) {return x/=thr,y/=thr,*this;}
}P[10010],ans,now;
inline LD dist(const POINT&one,const POINT&thr)
{
return sqrt(pow(one.x-thr.x,2)+pow(one.y-thr.y,2));
}
inline LD getrand()
{
return rand()/(LD)RAND_MAX;
}
inline LD getrand2()
{
return getrand()*2-1;
}
static int n; LD mns=1e100,w[10010];
inline LD check(const POINT&now)
{
LD ret=0; REP(i,1,n) ret+=dist(now,P[i])*w[i];
if(ret<mns) mns=ret,ans=now; return ret;
}
int main()
{
srand(time(0)),ios::sync_with_stdio(0),cin>>n; LD s=0;
REP(i,1,n) P[i].input(),cin>>w[i],now+=P[i]*w[i],s+=w[i];
check(now/=s); for(LD T=1e5;T>eps;T*=0.99)
{
POINT nxt(now.x+T*getrand2(),now.y+T*getrand2());
LD det=check(now)-check(nxt);
if(det+eps>0||exp(det/T)>getrand()) now=nxt;
}
REP(i,1,1000)
{
check(POINT(ans.x+eps*getrand2(),ans.y+eps*getrand2()));
}
return ans.output(),0;
}
wxh @ 2017-02-08 15:58:14
[ Quote ] [ Edit ] [ Delete ] 2#
bzoj不能time(0)...
spacetime @ 2017-02-08 18:48:25
[ Quote ] [ Edit ] [ Delete ] 3#
回复wxh:orz。。受教了蟹蟹
ycyzcf @ 2018-03-16 11:07:16
[ Quote ] [ Edit ] [ Delete ] 4#
无限RE+1...没有用time(0)...qwq
kafuuchino01 @ 2018-10-16 22:03:36
[ Quote ] [ Edit ] [ Delete ] 5#
+1
[Top] [Previous Page] [Next Page]

HOME Back