題目描述

分析：

題目中說的“可以看見”means 在折線的每段所在直線朝x軸正方向，直線的左邊一片區(qū)域（其實(shí)就是折線的每段所在直線的上面）
所以我們要求的就是此題折線所在直線相交構(gòu)成的一個(gè)底朝下的凸殼(類似二次函數(shù)a>0的樣子)，網(wǎng)上都說這個(gè)是求半平面交，這里就不那么高大上了，直接求吧。

Solution ：

先對Lines按照斜率大小排序，用一個(gè)棧來維護(hù)形成凸殼的直線。

• 如果當(dāng)前直線與stack [top-2] (棧的倒數(shù)第二個(gè)元素)的交點(diǎn)橫坐標(biāo)小于stack [top-1]與stack [top-2] 的交點(diǎn)橫坐標(biāo)，那么stack [top-1]這個(gè)元素出隊(duì)(依據(jù)是：當(dāng)前的直線相對倒數(shù)第一條直線對倒數(shù)第二條直線更優(yōu)，就不要倒數(shù)第一條了)
• 特別注意如果有斜率相等的直線要取與y軸截距最大的那條，而且不能算交點(diǎn)！！

因?yàn)榍蟮檬莾啥握劬€之間的距離，顯然距離的計(jì)算可以表示為分段函數(shù)，而每一段函數(shù)都是一次函數(shù)的形式，那么距離也應(yīng)該是一次函數(shù)的形式(或者常函數(shù))，極值都是在折線的交點(diǎn)(折點(diǎn))處取。
分為兩個(gè)部分算。

• Part 1：凸殼折點(diǎn)對應(yīng)的距離
• Part 2：題目給出的折線的折點(diǎn)對應(yīng)的距離。

#include<cstdio> #include<cmath> #include<algorithm> using namespace std; #define MAXN 300 const double eps=1e-12; const double INF=1e20;struct Point{int x,y; }a[MAXN+10]; struct Line{double k,b; }L[MAXN+10],stak[MAXN+10];int n,top; double ans=INF,cro[MAXN+10];double Getk(Point a,Point b){return 1.0*(a.y-b.y)/(a.x-b.x); } void read() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i].x);for(int i=1;i<=n;i++)scanf("%d",&a[i].y);for(int i=1;i<n;i++){L[i].k=Getk(a[i],a[i+1]);L[i].b=1.0*a[i].y-1.0*a[i].x*L[i].k;} } bool cmp(Line a,Line b){if(fabs(a.k-b.k)<eps) return a.b<b.b;return a.k<b.k; } double GetCrossP(Line a,Line b){ //Get Crossover Pointreturn (a.b-b.b)/(b.k-a.k); } void GetConvex() {sort(L+1,L+n,cmp);stak[top++]=L[1];for(int i=2;i<n;i++){while(top){if(fabs(stak[top-1].k-L[i].k)<eps) top--;else if(top>1&&GetCrossP(L[i],stak[top-2])<=GetCrossP(stak[top-2],stak[top-1]))top--;elsebreak;}stak[top++]=L[i];} } double Gety(Line a,double x0){return a.k*x0+a.b; } void Getans() {//Part 1for(int i=1;i<top;i++){double x0=GetCrossP(stak[i-1],stak[i]);cro[i]=x0;int k=-1;for(int j=1;j<n;j++)if(x0<=1.0*a[j+1].x){k=j;break;}if(k==-1) continue;Line t;t.k=Getk(a[k],a[k+1]);t.b=1.0*a[k].y-1.0*a[k].x*t.k;double tmp=Gety(stak[i],x0)-Gety(t,x0);if(tmp>=0.0)ans=min(ans,tmp);}//Part 2for(int i=1;i<=n;i++){int k=-1;for(int j=1;j<top;j++)if(1.0*a[i].x<=cro[j]){k=j-1;break;}if(k==-1) continue;double tmp=Gety(stak[k],1.0*a[i].x)-1.0*a[i].y;if(tmp>=0.0)ans=min(ans,tmp);}printf("%.3lf\n",ans); } int main() {read();GetConvex();Getans();return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/katarinayuan/p/6572821.html

總結(jié)

以上是生活随笔為你收集整理的HYSBZ/BZOJ 1038 [ZJOI2008] 瞭望塔 - 计算几何的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。