【BZOJ1038】【ZJOJ2008】瞭望塔

真实的flag：

然后还真是\(nlogn\)的半平面交

首先我们可以用半平面交求出可行塔顶区域

然后因为距离是个分段一次函数。。所以极值一定在断点上

也就是凸包的顶点或者原来某个村子处

数据范围太小了随便算一下就行了

// <1038.cpp> - Tue Mar  7 11:18:03 2017
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <complex>
using namespace std;
typedef long long lol;
typedef long double lod;
typedef complex <lod> pt;
template<typename T>
inline void gg(T &res){
    res=0;T fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    res*=fh;
}
inline int gi(){int x;gg(x);return x;}
inline lol gl(){lol x;gg(x);return x;}
const int MAXN=310;
const lod INF=1e14;
const lod eps=1e-6;
struct hp{pt x,y;lod k;}h[MAXN];
inline int sgn(lod x){return fabs(x)<eps?0:x>0?1:-1;}
inline lod cross(pt a,pt b){return (conj(a)*b).imag();}
inline bool in(pt p,hp &a){return sgn(cross(a.y-a.x,p-a.x))>=0;}
inline pt meet(hp a,hp b){
    lod k1=cross(b.x-a.x,a.y-a.x);
    lod k2=cross(a.y-a.x,b.y-a.x);
    return b.x+k1/(k1+k2)*(b.y-b.x);
}
bool cmp(hp a,hp b){
    int r=sgn(a.k-b.k);
    return r?r<0:in(a.x,b);
}
bool eq(hp a,hp b){return !sgn(a.k-b.k);}
int n,m,q[MAXN],l,r,L,R;
pt a[MAXN],c[MAXN];
void work(){
    l=1,r=0,L=1,R=0;
    q[++r]=1;
    for(int i=2;i<=m;i++){
        while(l<r&&!in(c[R],h[i]))r--,R--;
        while(l<r&&!in(c[L],h[i]))l++,L++;
        c[++R]=meet(h[i],h[q[r]]);
        q[++r]=i;
    }
    while(l<r&&!in(c[R],h[q[l]]))r--,R--;
    while(l<r&&!in(c[L],h[q[r]]))l++,L++;
    c[++R]=meet(h[q[l]],h[q[r]]);
}
lod get(pt a,pt l,pt r){
    if(a.real()<l.real()||r.real()<a.real())return INF;
    return fabs(meet((hp){l,r},(hp){a,pt(a.real(),INF)}).imag()-a.imag());
}
int main(){
    n=gi();
    for(int i=1;i<=n;i++)a[i]+=pt(gi(),0);
    for(int i=1;i<=n;i++)a[i]+=pt(0,gi());
    h[++m]=(hp){pt(INF,INF),pt(-INF,INF)};
    for(int i=1;i<n;i++)h[++m]=(hp){a[i],a[i+1]};
    for(int i=1;i<=m;i++)h[i].k=arg(h[i].y-h[i].x);
    sort(h+1,h+m+1,cmp);
    m=unique(h+1,h+m+1,eq)-h-1;
    work();
    lod ans=INF;
    for(int i=1;i<=n;i++){
        for(int j=L;j<R;j++)ans=min(ans,get(a[i],c[j],c[j+1]));
        ans=min(ans,get(a[i],c[R],c[L]));
    }
    for(int i=L;i<=R;i++)
        for(int j=1;j<n;j++)ans=min(ans,get(c[i],a[j],a[j+1]));
    printf("%.3Lf",ans);
    return 0;
}

// <1038.cpp> - Tue Mar 7 11:18:03 2017

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <complex>

using namespace std;

typedef long long lol;

typedef long double lod;

typedef complex <lod> pt;

template<typename T>

inline void gg(T &res){

res=0;T fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

res*=fh;

}

inline int gi(){int x;gg(x);return x;}

inline lol gl(){lol x;gg(x);return x;}

const int MAXN=310;

const lod INF=1e14;

const lod eps=1e-6;

struct hp{pt x,y;lod k;}h[MAXN];

inline int sgn(lod x){return fabs(x)<eps?0:x>0?1:-1;}

inline lod cross(pt a,pt b){return (conj(a)*b).imag();}

inline bool in(pt p,hp &a){return sgn(cross(a.y-a.x,p-a.x))>=0;}

inline pt meet(hp a,hp b){

lod k1=cross(b.x-a.x,a.y-a.x);

lod k2=cross(a.y-a.x,b.y-a.x);

return b.x+k1/(k1+k2)*(b.y-b.x);

}

bool cmp(hp a,hp b){

int r=sgn(a.k-b.k);

return r?r<0:in(a.x,b);

}

bool eq(hp a,hp b){return !sgn(a.k-b.k);}

int n,m,q[MAXN],l,r,L,R;

pt a[MAXN],c[MAXN];

void work(){

l=1,r=0,L=1,R=0;

q[++r]=1;

for(int i=2;i<=m;i++){

while(l<r&&!in(c[R],h[i]))r--,R--;

while(l<r&&!in(c[L],h[i]))l++,L++;

c[++R]=meet(h[i],h[q[r]]);

q[++r]=i;

}

while(l<r&&!in(c[R],h[q[l]]))r--,R--;

while(l<r&&!in(c[L],h[q[r]]))l++,L++;

c[++R]=meet(h[q[l]],h[q[r]]);

}

lod get(pt a,pt l,pt r){

if(a.real()<l.real()||r.real()<a.real())return INF;

return fabs(meet((hp){l,r},(hp){a,pt(a.real(),INF)}).imag()-a.imag());

}

int main(){

n=gi();

for(int i=1;i<=n;i++)a[i]+=pt(gi(),0);

for(int i=1;i<=n;i++)a[i]+=pt(0,gi());

h[++m]=(hp){pt(INF,INF),pt(-INF,INF)};

for(int i=1;i<n;i++)h[++m]=(hp){a[i],a[i+1]};

for(int i=1;i<=m;i++)h[i].k=arg(h[i].y-h[i].x);

sort(h+1,h+m+1,cmp);

m=unique(h+1,h+m+1,eq)-h-1;

work();

lod ans=INF;

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

for(int j=L;j<R;j++)ans=min(ans,get(a[i],c[j],c[j+1]));

ans=min(ans,get(a[i],c[R],c[L]));

}

for(int i=L;i<=R;i++)

for(int j=1;j<n;j++)ans=min(ans,get(c[i],a[j],a[j+1]));

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

return 0;

}