首页 > 代码库 > HDU 3644
HDU 3644
模拟退火算法。。。。
这道题,呃。我怎么感觉他就是随机的。同一个代码,时而AC,时而WA。其实还真的是随机的。呵呵呵呵呵。。。因为下降火太快了,没办法,而降得慢又会。。。TLE,虽然精度提高了。
敢问,还有什么好的方法?我是在做退火算法时遇到这个练手的。
#include <iostream>#include <cmath>#include <cstdio>#include <algorithm>#include <cstring>#include <time.h>using namespace std;const int MAXN=55;const double PI=3.141592653;const double eps=1e-5;#define zero(a) fabs(a)<epsstruct point { double x,y;};struct Segment{ point a,b;};point p[MAXN]; int n; double ans; int cot;point tar[MAXN]; double best[MAXN]; double R;point operator -(point &u,point &v){ point re; re.x=u.x-v.x; re.y=u.y-v.y; return re;}double dot(point &u,point &v){ return u.x*v.x+u.y*v.y;}double dist(point tt){ return sqrt(tt.x*tt.x+tt.y*tt.y);}double multi(point &u,point &v){ return u.x*v.y-u.y*v.x;}/*bool whether_in(point &t){ double angle=0; for(int i=0;i<n;i++){ point A=p[i]-t; point B=p[i+1]-t; angle+=acos(dot(A,B)/dist(A)/dist(B)); } if(fabs(angle-PI*2)<1e-5) return true; return false;}*/double xmul(point p0,point p1,point p2){ return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); }bool online(point p1,point p2,point p){ if(zero(xmul(p1,p2,p))&&((p.x-p1.x)*(p.x-p2.x)<eps&&(p.y-p1.y)*(p.y-p2.y)<eps)) return true; return false; }inline bool across(Segment s1,Segment s2){ if(xmul(s1.a,s1.b,s2.a)*xmul(s1.a,s1.b,s2.b)<eps) if(xmul(s2.a,s2.b,s1.a)*xmul(s2.a,s2.b,s1.b)<eps) return true; return false; }bool whether_in(point cen){ int cnt=0; Segment s,e; s.a=cen;s.b.y=cen.y;s.b.x=20000.0; for(int i=0;i<n;i++){ e.a=p[i];e.b=p[i+1]; if(online(p[i],p[i+1],cen)) return false; if(zero(p[i].y-p[i+1].y)) continue; if(online(s.a,s.b,p[i])){ if(p[i].y>p[i+1].y) cnt++; } else if(online(s.a,s.b,p[i+1])){ if(p[i+1].y>p[i].y) cnt++; } else if(across(s,e)) cnt++; } return cnt&1; }double count_d(point &tt){ double mm=1e10; double tp; for(int i=0;i<n;i++){ point A=tt-p[i]; point B=p[i+1]-p[i]; if(dot(A,B)<=0){ tp=dist(A); // cout<<"1"<<‘ ‘<<tp<<endl; mm=min(mm,tp); continue; } A=tt-p[i+1]; B=p[i]-p[i+1]; if(dot(A,B)<=0){ tp=dist(A); mm=min(mm,tp); // cout<<"2"<<‘ ‘<<tp<<endl; continue; } double area=multi(A,B); tp=fabs(area)/dist(p[i]-p[i+1]); // cout<<"3"<<‘ ‘<<tp<<endl; mm=min(mm,tp); } return mm;}double getdouble(){ double re=((rand()*rand())%1000000)*1.0/1e6; return re;}int main(){ srand(time(0)); while(scanf("%d",&n),n){ cot=0; for(int i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); scanf("%lf",&R); p[n]=p[0]; point tmp; for(int i=0;i<n;i++){ tmp.x=(p[i].x+p[i+1].x)/2; tmp.y=(p[i].y+p[i+1].y)/2; tar[cot++]=tmp; } // cout<<cot<<endl; bool flag=false; for(int i=0;i<cot;i++){ best[i]=0; } // cout<<"YES"<<endl; double T=50; for(double t=T;t>1e-4;t*=0.55){ for(int i=0;i<cot;i++){ for(int j=0;j<10;j++){ double td=getdouble(); if(rand()&1) td*=-1; tmp.x=tar[i].x+td*t; td=getdouble(); if(rand()&1) td*=-1; tmp.y=tar[i].y+td*t; if(whether_in(tmp)){ td=count_d(tmp); if(td>best[i]){ best[i]=td; tar[i]=tmp; } if(td>=R||fabs(td-R)<1e-4){ // cout<<tmp.x<<‘ ‘<<tmp.y<<endl; // cout<<td<<endl; flag=true; break; } } } if(flag) break; } if(flag) break; } if(flag) printf("Yes\n"); else printf("No\n"); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。