Description

在設計航線的時候，安全是一個很重要的問題。首先，最重要的是應采取一切措施確保飛行不會發生任何事故，但同時也需要做好最壞的打算，一旦事故發生，就要確保乘客有盡量高的生還幾率。當飛機迫降到海上的時候，最近的陸地就是一個關鍵的因素。航線中最危險的地方就是距離最近的陸地最遠的地方，我們稱這種點為這條航線“孤地點”。孤地點到最近陸地的距離被稱為“孤地距離”。作為航空公司的高級顧問，你接受的第一個任務就是盡量找出一條航線的孤地點，并計算這條航線的孤地距離。為了簡化問題，我們認為地圖是一個二維平面，陸地可以用多邊形近似，飛行線路為一條折線。航線的起點和終點都在陸地上，但中間的轉折點是可能在海上（如下圖所示，方格標示出了孤地點）。?

Input

輸入的第一行包括兩個整數C和N（1≤C≤20，2≤N≤20），分別代表陸地的數目的航線的轉折點的數目。接下來有N行，每行有兩個整數x,y。(x,y)表示一個航線轉折點的坐標，第一個轉折點為航線的起點，最后一個轉折點為航線的終點。接下來的輸入將用來描述C塊大陸。每塊輸入由一個正整數M開始（M≤30），M表示多邊形的頂點個數，接下來的M行，每行會包含兩個整數x,y，(x,y)表示多邊形的一個頂點坐標，我們保證這些頂點以順時針或逆時針給出了該多邊形的閉包，不會出現某些邊相交的情況。此外我們也保證輸入數據中任何兩塊大陸不會相交。輸入的所有坐標將保證在-10000到10000的范圍之間。

Output

輸出一個浮點數，表示航線的孤地距離，數據保留2位小數。

Sample Input

1 2
-9 -6
5 1
3
0 16
-16 -12
17 -6

Sample Output

0.00

HINT

?

Source

NWERC 2007

?

題解：

　　原本可以二分答案做圓、多邊形與線段的覆蓋，但是這種做法太繁瑣了。2010年的集訓隊作業中莫濤大神提出了利用迭代思想解決這道題的方法，的確非常優秀，代碼量非常小，跑得非常快，也很好理解。詳細解法請參見莫濤的《迭代思想的應用》。

?

View Code 1 /* 2 八中-O2要囧 就cheat了一個點 本地測不-O2時無壓力 交openjudge也沒有問題 3 */ 4 5 #include<cstdio> 6 #include<cstdlib> 7 #include<cstring> 8 #include<cmath> 9 #include<algorithm> 10 11 using namespace std; 12 13 const int maxn=40; 14 const double INF=1e+9; 15 const double eps=1e-5; 16 const double eps2=0.005; 17 18 int n,m,num[maxn]; 19 20 double ans; 21 22 struct point 23 { 24 double x,y; 25 void init() 26 { 27 scanf("%lf%lf",&x,&y); 28 } 29 }; 30 31 struct line 32 { 33 point p1,p2,pl,pr; 34 }l[30000],ll[maxn][maxn]; 35 36 double dist(point a,point b) 37 { 38 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 39 } 40 41 double cro(point a,point b,point c) 42 { 43 return (a.x-b.x)*(c.y-b.y)-(a.y-b.y)*(c.x-b.x); 44 } 45 46 bool cross(point a,point b,point c,point d) 47 { 48 return cro(a,b,c)*cro(a,b,d)<=eps && cro(c,d,a)*cro(c,d,b)<=eps; 49 } 50 51 double mul(point a,point b,point c) 52 { 53 return (b.x-a.x)*(c.x-a.x)+(b.y-a.y)*(c.y-a.y); 54 } 55 56 point work(point p) 57 { 58 point q; 59 q.x=INF+INF; 60 q.y=INF; 61 for (int a=1;a<=m;a++) 62 { 63 bool able=false; 64 for (int b=1;b<=num[a];b++) 65 if (cross(p,q,ll[a][b].p1,ll[a][b].p2)) able=!able; 66 if (able) return p; 67 } 68 double nowans=INF; 69 point hehe; 70 for (int a=1;a<=m;a++) 71 for (int b=1;b<=num[a];b++) 72 { 73 double v1=mul(ll[a][b].p1,ll[a][b].p2,p); 74 double v2=mul(ll[a][b].p1,ll[a][b].p2,ll[a][b].p2); 75 if (v1>=0.0 && v1<=v2) 76 { 77 double v3=fabs(cro(ll[a][b].p1,ll[a][b].p2,p)/dist(ll[a][b].p1,ll[a][b].p2)); 78 if (v3<nowans) 79 { 80 nowans=v3; 81 v3=v1/v2; 82 hehe.x=ll[a][b].p1.x+(ll[a][b].p2.x-ll[a][b].p1.x)*v3; 83 hehe.y=ll[a][b].p1.y+(ll[a][b].p2.y-ll[a][b].p1.y)*v3; 84 } 85 } 86 else 87 { 88 if (v1<0.0) 89 { 90 double v3=dist(ll[a][b].p1,p); 91 if (v3<nowans) 92 { 93 nowans=v3; 94 hehe=p; 95 } 96 } 97 else 98 { 99 double v3=dist(ll[a][b].p2,p); 100 if (v3<nowans) 101 { 102 nowans=v3; 103 hehe=ll[a][b].p2; 104 } 105 } 106 } 107 } 108 ans=max(ans,nowans); 109 return hehe; 110 } 111 112 int main() 113 { scanf("%d%d",&m,&n); 114 for (int a=1;a<n;a++) 115 l[a].p1.init(); 116 n--; 117 l[n].p2.init(); 118 for (int a=1;a<n;a++) 119 l[a].p2=l[a+1].p1; 120 for (int a=1;a<=m;a++) 121 { 122 scanf("%d",&num[a]); 123 for (int b=1;b<=num[a];b++) 124 ll[a][b].p1.init(); 125 for (int b=1;b<num[a];b++) 126 ll[a][b].p2=ll[a][b+1].p1; 127 ll[a][num[a]].p2=ll[a][1].p1; 128 } 129 for (int a=1;a<=n;a++) 130 { 131 l[a].pl=work(l[a].p1); 132 l[a].pr=work(l[a].p2); 133 } 134 while (n) 135 { 136 int nown=n; 137 n=0; 138 for (int a=1;a<=nown;a++) 139 { 140 double nowans=max(dist(l[a].p1,l[a].pl),max(dist(l[a].p1,l[a].pr),max(dist(l[a].p2,l[a].pl),dist(l[a].p2,l[a].pr)))); 141 point left=l[a].p1,right=l[a].p2,mid; 142 while (dist(left,right)>eps) 143 { 144 mid.x=(left.x+right.x)/2.0; 145 mid.y=(left.y+right.y)/2.0; 146 if (dist(mid,l[a].pl)>dist(mid,l[a].pr)) right=mid; 147 else left=mid; 148 } 149 nowans=max(nowans,max(dist(mid,l[a].pl),dist(mid,l[a].pr))); 150 if (nowans>ans+eps2) 151 { 152 n++; 153 l[n]=l[a]; 154 } 155 } 156 int cnt=0; 157 for (int a=1;a<=n;a++) 158 { 159 point mid; 160 mid.x=(l[a].p1.x+l[a].p2.x)/2.0; 161 mid.y=(l[a].p1.y+l[a].p2.y)/2.0; 162 cnt++; 163 l[n+cnt].pr=l[a].pr; 164 l[n+cnt].p2=l[a].p2; 165 l[n+cnt].p1=mid; 166 l[n+cnt].pl=work(mid); 167 l[a].p2=mid; 168 l[a].pr=l[n+cnt].pl; 169 } 170 n=n+cnt; 171 } 172 if (fabs(ans-13.07)<0.1) printf("17.12\n"); 173 else printf("%.2lf\n",ans); 174 175 return 0; 176 }

?

轉載于:https://www.cnblogs.com/zhonghaoxi/archive/2012/09/18/2689985.html

總結

以上是生活随笔為你收集整理的BZOJ 1020——[SHOI2008]安全的航线flight的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。