半平面交后,可能成为答案的点就是凸包上的点 和 山峰(分段函数的分段点).
枚举一下就行了.
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-10;
const int MAXN = 505;
inline double sqr(double x) { return x*x; }
inline double dcmp(double x) {
if(x < -eps) return -1;
if(x > eps) return 1;
return 0;
}
struct Point {
double x, y;
Point(){}
Point(const double &x, const double &y):x(x), y(y){}
inline Point operator +(const Point &o)const { return Point(x + o.x, y + o.y); }
inline Point operator -(const Point &o)const { return Point(x - o.x, y - o.y); }
inline Point operator *(const double &k)const { return Point(x * k, y * k); }
inline double operator *(const Point &o)const { return x * o.y - y * o.x; }
inline friend double dist(const Point &A, const Point &B) { return sqrt(sqr(A.x-B.x) + sqr(A.y-B.y)); }
}P[MAXN];
struct Line {
Point p, v; double angle;
Line(){}
Line(const Point &p, const Point &v):p(p), v(v){
angle = atan2(v.y, v.x);
}
inline friend bool On_Right(const Line &l, const Point &p) {
return dcmp(l.v * (p - l.p)) <= 0;
}
inline bool operator <(const Line &o)const {
if(!dcmp(angle-o.angle))
return dcmp(v * (o.p - p)) < 0;
return angle < o.angle;
}
inline friend Point Get_Intersection(const Line &l1, const Line &l2) {
Point u = l1.p - l2.p;
double k = (l2.v * u) / (l1.v * l2.v);
return l1.p + l1.v * k;
}
inline double f(double x) {
return p.y + (x-p.x)/v.x * v.y;
}
}arr[MAXN], q[MAXN]; int top;
inline void Insert(const Line &l) {
while(top > 1 && On_Right(l, Get_Intersection(q[top-1], q[top]))) --top;
q[++top] = l;
}
int n, m, tot;
double x[MAXN], y[MAXN];
inline double f(double X) {
double re = 0;
for(int i = 1; i <= top; ++i)
re = max(re, q[i].f(X));
return re;
}
inline double g(double X) {
int i = upper_bound(x + 1, x + n + 1, X) - x - 1;
return y[i] + (X-x[i])/(x[i+1]-x[i])*(y[i+1]-y[i]);
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%lf", &x[i]);
for(int i = 1; i <= n; ++i) {
scanf("%lf", &y[i]);
if(i > 1) arr[++tot] = Line(Point(x[i-1], y[i-1]), Point(x[i]-x[i-1], y[i]-y[i-1]));
}
sort(arr + 1, arr + tot + 1);
q[++top] = arr[1];
for(int i = 2; i <= tot; ++i)
if(dcmp(arr[i].angle-arr[i-1].angle))
Insert(arr[i]);
double ans = 1e15;
for(int i = 1; i <= n; ++i)
ans = min(ans, f(x[i]) - y[i]);
for(int i = 2; i <= top; ++i) {
Point now = Get_Intersection(q[i], q[i-1]);
ans = min(ans, now.y - g(now.x));
}
printf("%.3f
", ans);
}