首页 > 代码库 > 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;}