真实的flag：
然后还真是\(nlogn\)的半平面交
首先我们可以用半平面交求出可行塔顶区域
然后因为距离是个分段一次函数。。所以极值一定在断点上
也就是凸包的顶点或者原来某个村子处
数据范围太小了 随便算一下就行了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
// <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; } |
说点什么