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;
}