NC20480. [ZJOI2008]瞭望塔
描述
输入描述
第一行包含一个整数n，表示轮廓折线的节点数目。接下来第一行n个整数, 为x1~ xn。第三行n个整数，为y1 ~ yn。
输出描述
仅包含一个实数，为塔的最小高度，精确到小数点后三位。
示例1
输入:
6 1 2 4 5 6 7 1 2 2 4 2 1
输出:
1.000
示例2
输入:
4 10 20 49 59 0 10 10 0
输出:
14.500
C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 428K, 提交时间: 2022-09-21 19:37:01
#include<bits/stdc++.h>
using namespace std;
#define db double
#define ll long long
#define eb emplace_back
using _T = db;
const _T eps = 1e-12, inf = 1e12;
const int MAXN = 300 + 5;
template<typename T> struct tpoint
{
T x,y;
tpoint(T x,T y):x(x),y(y){};
tpoint(){};
bool operator == (const tpoint &p) const { return fabs(x-p.x)<eps && fabs(y-p.y)<eps; }
bool operator < (const tpoint &p) const { if(fabs(x-p.x)<eps) return y<p.y-eps; return x<p.x-eps; }
tpoint operator + (const tpoint &p) const { return tpoint(x+p.x,y+p.y); }
tpoint operator - (const tpoint &p) const { return tpoint(x-p.x,y-p.y); }
tpoint operator * (const T d) const { return tpoint(x*d,y*d); }
T operator * (const tpoint &p) const { return x*p.x+y*p.y; }
T operator ^ (const tpoint &p) const { return x*p.y-p.x*y; }
int toleft (const tpoint &p) const { auto t=(*this)^p; return (t>eps)-(t<-eps); }
db dis(const tpoint &p) const { return sqrt((*this-p)*(*this-p)); }
void show() { printf("point: %.7f %.7f\n",x,y); }
};
using point = tpoint<_T>;
point p = point(0,0),p0(0,1),p1,p2;
template<typename T> struct tline
{
point p,v;
tline(point p, point v):p(p),v(v){};
tline(){};
bool operator == (const tline &l) const { return v.toleft(l.v)==0 && v.toleft(p-l.p)==0; }
bool operator < (const tline &l) const
{
int k1,k2;
if(v.x > eps || (fabs(v.x)<eps && v.y > eps)) k1 = 0;
else k1 = 1;
if(l.v.x > eps || (fabs(l.v.x)<eps && l.v.y > eps)) k2 = 0;
else k2 = 1;
if(k1 != k2) return k1 < k2;
if(v.toleft(l.v) == 0) return v.toleft(l.p-p) < 0;
return l.v.toleft(v) < 0;
}
int toleft(const point &a) const { return v.toleft(a-p); }
point inter(const tline &l) const { return p+v*((l.v^(l.p-p))/(l.v^v)); }
void show() { printf("line: %.7f %.7f %.7f %.7f\n",p.x,p.y,v.x,v.y); }
};
using line = tline<_T>;
line l;
vector<point> points,convexs;
vector<line> lines,halfs;
ll hfok,ind[MAXN+5],hfdq[MAXN+5];
bool cmp(ll x, ll y) { return lines[x] < lines[y]; }
bool halfcheck(line &l1, line &l2, line &l3)
{
return l1.toleft(l2.inter(l3)) <= 0;
}
void halfini(ll mn, _T inf)
{
if(hfok) return;
lines[mn+1] = line(point(-inf,0),point(0,-1));
lines[mn+2] = line(point(0,-inf),point(1,0));
lines[mn+3] = line(point(inf,0),point(0,1));
lines[mn+4] = line(point(0,inf),point(-1,0));
hfok = 1;
}
ll halfplane(ll n, ll mn, _T inf)
{
ll sz=1,i,a,arrl=1,arrr=0;
point v;
for(i=1;i<=n;i++) ind[i] = i;
for(i=1;i<=4;i++) ind[n+i] = mn+i;
halfini(mn,inf);
sort(ind+1,ind+n+5,cmp);
for(i=1;i<=n+4;i++)
{
a = ind[i];
if(i>1 && lines[a].v.toleft(lines[ind[i-1]].v) == 0 && lines[a].v*lines[ind[i-1]].v>eps) continue;
while(arrr > arrl && halfcheck(lines[a],lines[hfdq[arrr]],lines[hfdq[arrr-1]])) arrr --;
while(arrr > arrl && halfcheck(lines[a],lines[hfdq[arrl]],lines[hfdq[arrl+1]])) arrl ++;
hfdq[++arrr] = a;
}
while(arrr > arrl && halfcheck(lines[hfdq[arrl]],lines[hfdq[arrr]],lines[hfdq[arrr-1]])) arrr --;
while(arrr > arrl && halfcheck(lines[hfdq[arrr]],lines[hfdq[arrl]],lines[hfdq[arrl+1]])) arrl ++;
halfs.resize(arrr-arrl+2);
for(i=arrl;i<=arrr;i++) halfs[sz++] = lines[hfdq[i]];
return sz-1;
}
int main()
{
ll i,n,m,arr1=0,arr2=1;
db ans = inf,temp;
scanf("%lld",&n);
points.resize(MAXN+5); lines.resize(MAXN+5);
for(i=1;i<=n;i++) scanf("%lf",&points[i].x);
for(i=1;i<=n;i++) scanf("%lf",&points[i].y);
for(i=1;i<n;i++) lines[i] = line(points[i],points[i+1]-points[i]);
//printf("ok!\n");
m = halfplane(n-1,MAXN,inf);
//printf("m: %lld\n",m);
convexs.resize(m);
for(i=1;i<=m;i++)
{
convexs[i-1] = halfs[i].inter(halfs[i%m+1]);
//convexs[i-1].show();
}
sort(convexs.begin(),convexs.end());
points[n+1].x = 1e6+1; points[n+1].y = 0;
while(arr2 <= n)
{
l = line(point(min(points[arr2+1].x,convexs[arr1+1].x),0),p0);
p1 = l.inter(line(convexs[arr1],convexs[arr1+1]-convexs[arr1]));
p2 = l.inter(line(points[arr2],points[arr2+1]-points[arr2]));
//p1.show(); p2.show();
//printf("%lld %lld\n\n",arr1,arr2);
temp = p1.y - p2.y;
ans = min(ans,temp);
if(points[arr2+1].x > convexs[arr1+1].x) arr1 ++;
else arr2 ++;
}
printf("%.3f",max((double)0,ans));
return 0;
}
/*
6
1 2 4 5 6 7
1 2 2 5 2 1
*/
C++14(g++5.4) 解法, 执行用时: 6ms, 内存消耗: 488K, 提交时间: 2020-04-11 23:03:32
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
int top = 0;
double ans;
int s[400];
int N;
struct node {
double x, y;
} n[400];
inline LL read()
{
LL x = 0, w = 1; char ch = 0;
while(ch < '0' || ch > '9') {
if(ch == '-') {
w = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * w;
}
struct line {
double k;
double b;
} l[400];
bool cmp(line a, line b)
{
if(a.k == b.k) {
return a.b > b.b;
}
return a.k < b.k;
}
double intersaction(int a, int b)
{
return (l[a].b - l[b].b) / (l[b].k - l[a].k);
}
int main()
{
N = read();
for(int i = 1; i <= N; i++) {
n[i].x = read();
}
for(int i = 1; i <= N; i++) {
n[i].y = read();
}
for(int i = 2; i <= N; i++) {
l[i - 1].k = (n[i].y - n[i - 1].y) / (n[i].x - n[i - 1].x);
l[i - 1].b = n[i].y - n[i].x * l[i - 1].k;
}
sort(l + 1, l + N, cmp);
s[0] = 1;
top = 1;
for(int i = 2; i < N; i++) {
if(l[i].k == l[i - 1].k) {
continue;
}
while(top > 1 && intersaction(i, s[top - 1]) <= intersaction(s[top - 1], s[top - 2])) {
top--;
}
s[top++] = i;
}
ans = 1e17;
int t = 1;
for(int i = 0; i < top - 1; i++) {
double x = intersaction(s[i], s[i + 1]);
while(n[t].x < x && t < N) {
ans = min(ans, l[s[i]].k * n[t].x + l[s[i]].b - n[t].y);
t++;
}
x = min(x, n[N].x);
double kk = (n[t].y - n[t - 1].y) / (n[t].x - n[t - 1].x);
ans = min(ans, l[s[i]].k * x + l[s[i]].b - kk * x - (n[t].y - kk * n[t].x));
if(x == n[N].x) {
break;
}
}
printf("%.3lf\n", ans);
return 0;
}
/*
6
1 2 4 5 6 7
1 2 2 4 2 1
4
10 20 49 59
0 10 10 0
*/
C++ 解法, 执行用时: 33ms, 内存消耗: 440K, 提交时间: 2022-03-10 22:27:37
#include <bits/stdc++.h>
using namespace std;
const int N=305;
const double inf=1e11-1.0;
int n;
double ax[N],ay[N];
double ans=inf;
struct LINE{
double k,b; //y=kx+b
}height[N];
double sol(double x){
double res=0;
for(int i=1;i<n;i++)
res=max(res,height[i].k*x+height[i].b);
return res;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>ax[i];
for(int i=1;i<=n;i++)
cin>>ay[i];
for(int i=1;i<n;i++){
height[i].k=(ay[i]-ay[i+1])/(ax[i]-ax[i+1]);
height[i].b=ay[i]-height[i].k*ax[i];
}
for(int i=1;i<=n;i++)
ans=min(ans,sol(ax[i])-ay[i]); //先枚举每个端点
for(int i=1;i<n;i++)
for(int j=i+1;j<n;j++){
double x=(height[i].b-height[j].b)/(height[j].k-height[i].k); //求两直线的交点
for(int k=1;k<n;k++)
if(ax[k]<=x&&x<=ax[k+1])
ans=min(ans,sol(x)-height[k].k*x-height[k].b); //最小化答案
}
printf("%.3lf\n",ans);
return 0;
}