首页 > 代码库 > BZOJ 3680 吊打XXX 模拟退火
BZOJ 3680 吊打XXX 模拟退火
首先这题应该改名叫吊打出题人
题目大意:给定n个质点,求重心
这n个质点的重心满足Σ(重心到点i的距离)*g[i]最小
模拟退火的裸题
尼玛交了两篇 死活过不去 各种改参数 最后发现是我的INF不够大 尼玛!
这题INF开0x3f妥妥过不去。。。起码要max_of _long_long附近才可以
最后写了10188MS,BZOJ倒数第一……这也是种艺术啊0.0
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 10100 using namespace std; struct point{ double x,y,g; }points[M],ans; int n; double minans=23333333333333333ll; double dis(const point &x,const point &y) { return sqrt( (x.x-y.x)*(x.x-y.x) + (x.y-y.y)*(x.y-y.y) ); } double Judge(const point &p) { int i; double re=0; for(i=1;i<=n;i++) re+=points[i].g*dis(p,points[i]); if(re<minans) ans=p,minans=re; return re; } double Rand() { return rand()%1000/1000.0; } void SA(double T) { int i; point Now=ans; while(T>0.001) { point Neo; Neo.x=Now.x+T*(Rand()*2-1); Neo.y=Now.y+T*(Rand()*2-1); double dE = Judge(Now) - Judge(Neo) ; if( dE > 0 || exp(dE/T)>Rand() ) Now=Neo; T*=0.993; } for(i=1;i<=1000;i++) { point Neo; Neo.x=ans.x+T*(Rand()*2-1); Neo.y=ans.y+T*(Rand()*2-1); Judge(Neo); } } int main() { int i; srand(19970815); cin>>n; for(i=1;i<=n;i++) { scanf("%lf%lf%lf",&points[i].x,&points[i].y,&points[i].g); ans.x+=points[i].x; ans.y+=points[i].y; } ans.x/=n; ans.y/=n; SA( 1000000 ); printf("%.3lf %.3lf\n",ans.x,ans.y); }
BZOJ 3680 吊打XXX 模拟退火
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。