首页 > > 程序设计 > C/C++ >

bzoj1038 [ ZJOI2008 ] -- 模拟退火+二分

2018-06-17 22:58:15来源：未知阅读 ()

这题正解是半平面交，但可以用模拟退火水过。。。

用模拟退火求x的值，然后二分求y的值就可以了。

当所有端点到这个点的直线按逆时针顺序时这个点可以看到任何位置。

代码：

 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<algorithm>
 6 #include<cmath>
 7 using namespace std;
 8 #define N 310
 9 #define INF 1e11
10 #define Eps 1e-5
11 struct Node{
12     double x,y;
13     Node(){}
14     Node(double x,double y):x(x),y(y){}
15     Node operator - (Node a)const{
16         return Node(x-a.x,y-a.y);
17     }
18     double operator * (Node a)const{
19         return x*a.y-y*a.x;
20     }
21 }a[N],b[N];
22 double l,r,Mid,Ans=INF,Now,x,y,Ax,T,N2;
23 int i,j,k,n,m;
24 inline double Getrand(){
25     return rand()%1000/1000.0;
26 }
27 inline double Gety(double x){
28     for(int i=1;i<n;i++)
29     if(a[i+1].x>x)return (a[i+1].y-a[i].y)/(a[i+1].x-a[i].x)*(x-a[i].x)+a[i].y;
30 }
31 inline bool Check(Node A){
32     for(int i=1;i<n;i++)
33     if((A-a[i])*(A-a[i+1])<0)return 0;
34     return 1;
35 }
36 inline double Calc(double x){
37     double l=0,r=INF,Mid;
38     while(r-l>Eps){
39         Mid=(l+r)/2.0;
40         if(Check(Node(x,Mid)))r=Mid;else l=Mid;
41     }
42     l-=Gety(x);
43     if(l<Ans)Ans=l,Ax=x;
44     return l;
45 }
46 inline void SA(double T){
47     for(;T>0.00001;T*=0.99){
48         y=x+T*(Getrand()*2-1);
49         if(y<a[1].x||y>a[n].x)continue;
50         N2=Calc(x)-Calc(y);
51         if(N2>0||exp(N2/T)>Getrand())x=y;
52     }
53     for(int i=1;i<=1000;i++){
54         y=Ax+T*(Getrand()*2-1);
55         if(y<a[1].x||y>a[n].x)continue;
56         Calc(y);
57     }
58 }
59 int main(){
60     srand(30031);
61     scanf("%d",&n);
62     for(i=1;i<=n;i++)scanf("%lf",&a[i].x);
63     for(i=1;i<=n;i++)scanf("%lf",&a[i].y);
64     x=(a[1].x+a[n].x)/2.0;SA(100000);
65     printf("%.3lf",Ans+Eps);
66     return 0;
67 }