刷题总结——瞭望塔（bzoj1038）

题目：

Description

　　致力于建设全国示范和谐小村庄的H村村长dadzhi，决定在村中建立一个瞭望塔，以此加强村中的治安。我们
将H村抽象为一维的轮廓。如下图所示我们可以用一条山的上方轮廓折线(x1, y1), (x2, y2), …. (xn, yn)来描
述H村的形状，这里x1 < x2 < …< xn。瞭望塔可以建造在[x1, xn]间的任意位置, 但必须满足从瞭望塔的顶端可
以看到H村的任意位置。可见在不同的位置建造瞭望塔，所需要建造的高度是不同的。为了节省开支，dadzhi村长
希望建造的塔高度尽可能小。请你写一个程序，帮助dadzhi村长计算塔的最小高度。

Input

　　第一行包含一个整数n，表示轮廓折线的节点数目。接下来第一行n个整数, 为x1 ~ xn. 第三行n个整数，为y1
~ yn。

Output

　　仅包含一个实数，为塔的最小高度，精确到小数点后三位。

Sample Input

【输入样例一】
6
1 2 4 5 6 7
1 2 2 4 2 1
【输入样例二】
4
10 20 49 59
0 10 10 0

Sample Output

【输出样例一】
1.000
【输出样例二】
14.500

HINT

N ≤ 300，输入坐标绝对值不超过106，注意考虑实数误差带来的问题。

题解：

这里引用神犇我是傻叉（这名字··）的题解，ORZ，附上链接：http://blog.csdn.net/qpswwww/article/details/44105605

这个题在上海ACM/ICPC冬令营的比赛中也考过，不是很难，不过想要想到用半平面交来搞还是不容易的。

如上图，手模下可以发现一个点要想看到所有的山顶，肯定是要在相邻两个山顶连线的半平面交中。那么显然这个相对高度最小的点肯定是在半平面交的边界上，因此有如下两种情况：
1、这个点在半平面交边界上两个直线的交点处(代码中的calc2())
2、这个点在某个山顶在半平面交的边界的投影处(代码中的calc1())
可以脑补下，答案对应的点肯定是这两种情况之一，至于证明嘛。。。实在难以表述出来(谁会证明的请告诉我，感激不尽)

然后在代码的实现上偷了点小懒。。。之前翻其他人题解，无非就是两种做法：1、解析几何法求直线交点，2、叉积+定比分点公式求交，考虑到这个题的题面已经限制了没有两条直线垂直的情况（x1<x2<...<xn），加上最后要求相对高度时用解析几何法来得方便些，于是你懂的。

心得：

　　直线半平面交的经典题··和赛车有点相似之处，但tm又老wa一个点啊，md半平面交存心和我过不去吗？QWQ

另外还发现了一个写了赛车以来一直有的一个误解····就是凸多边形那个弹出check的方法是通用的！！！，赛车那道题是因为所有线都是射线！！所以可以那样化简而已，QWQ；

代码：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<ctime>

#include<cmath>

#include<algorithm>

#include<cctype>

#include<iomanip>

#define double long double

using namespace std;

int n,cnt,tot;

double ans;

struct P{

    double x,y;

}p[],a[];

P vec(P a,P b){

    P s;

    s.x=a.x-b.x;

    s.y=a.y-b.y;

    return s;

}

double xplus(P a,P b){

    return a.x*b.y-b.x*a.y;

}

struct L{

    P a,b;

    double slope;

    friend bool operator < (L aa,L ab){

        if(aa.slope!=ab.slope) return aa.slope<ab.slope;

        else return xplus(vec(aa.b,aa.a),vec(ab.b,aa.a))>;

    }

}l[],que[];

P inter(L a,L b){

    double k1,k2,t;

    k1=xplus(vec(b.b,a.a),vec(a.b,a.a));

    k2=xplus(vec(a.b,a.a),vec(b.a,a.a));

    t=k1/(k1+k2);

    P ret;

    ret.x=b.b.x+t*(b.a.x-b.b.x);

    ret.y=b.b.y+t*(b.a.y-b.b.y);

    return ret;

}

bool check(L a,L b,L t){

    P s=inter(a,b);

    return xplus(vec(t.b,t.a),vec(s,t.a))<;

}

void preact(){

    p[].x=p[].x,p[].y=;

    p[n+].x=p[n].x,p[n+].y=;

    for(int i=;i<=n;++i){

        l[++cnt].a=p[i-];l[cnt].b=p[i];

        l[++cnt].a=p[i];l[cnt].b=p[i+];

    }

    for(int i=;i<=cnt;++i)

        l[i].slope=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x);

    sort(l+,l+cnt+);

    return ;

}

void hpi(){

    int ll=,rr=;tot=;

    for(int i=;i<=cnt;++i){

        if(l[i].slope!=l[i-].slope) ++tot;

        l[tot]=l[i];

    }

    cnt=tot;tot=;

    que[++rr]=l[],que[++rr]=l[];

    for(int i=;i<=cnt;++i){

        while(ll<rr&&check(que[rr-],que[rr],l[i])) --rr;

        while(ll<rr&&check(que[ll+],que[ll],l[i])) ++ll;

        que[++rr]=l[i];

    }

    while(ll<rr&&check(que[rr-],que[rr],que[ll])) --rr;

    while(ll<rr&&check(que[ll+],que[ll],que[rr])) ++ll;

    for(int i=ll;i<rr;++i)

        a[++tot]=inter(que[i],que[i+]);

    return ;

}

void getans(){

    for(int i=;i<=tot;++i){

        P posnow;

        posnow.x=a[i].x;

        posnow.y=-;

        for(int j=;j<n;++j)

            if(a[i].x>=p[j].x&&a[i].x<=p[j+].x)

                ans=min(ans,a[i].y-inter((L){p[j],p[j+]},(L){posnow,a[i]}).y);

    }

    for(int i=;i<=n;++i){

        P nowpos;

        nowpos.x=p[i].x;

        nowpos.y=-;

        for(int j=;j<tot;++j)

            if(a[j].x<=p[i].x&&a[j+].x>=p[i].x)

                ans=min(ans,inter((L){a[j],a[j+]},(L){nowpos,p[i]}).y-p[i].y);

    }

    return ;

}

inline int read(){

    int i=,f=;

    char ch;

    for(ch=getchar();ch>''||ch<'';ch=getchar())

        if(ch=='-') f=-;

    for(;ch>=''&&ch<='';ch=getchar())

        i=(i<<)+(i<<)+(ch^);

    return i*f;

}

int main(){

    n=read();

    ans=1e60;

    for(int i=;i<=n;++i)

        p[i].x=read();

    for(int i=;i<=n;++i)

        p[i].y=read();

    preact();

    hpi();

    getans();

    printf("%.3Lf",ans);

    return ;

}

巴特西