#P15779. 王陵最短破壁路

王陵最短破壁路

题目描述

Geo 三世国王的陵墓是一座巨大的石质建筑,形状是一张直方图。这里的直方图指一个简单的正交多边形,它的边界由两条链组成:上边界是一条关于水平轴单调的折线,下边界是一条水平线段,称为基底线段。

一个直方图形状的陵墓、外部点 SS、内部宝藏点 TT,以及从 SS 经过边界顶点 a,b,ca,b,c 到达 TT 的若干候选路径。图中应标出坐标网格和顶点名称,这是样例 1 对应该图。

传说陵墓内部藏着宝藏。著名寻宝者 Metry 已经确定宝藏位于点 TT。她会从陵墓外部的某个点 SS 出发,用设备在陵墓边界上的一个顶点处钻入,然后进入内部取走宝藏。

设备只能在边界顶点处钻入,而且只能钻入一次。由于在任意顶点钻墙所需时间相同,需要最小化的是从 SS 到 TT 的路径长度,其中路径必须经过恰好一个陵墓边界顶点。

例如,原图中经过顶点 aa 的路径长度为

11.385165=6+29,11.385165=6+\sqrt{29},

经过顶点 bb 的路径长度为

10.077687=20+13+2,10.077687=\sqrt{20}+\sqrt{13}+2,

经过顶点 cc 的路径长度为

11.0=2+25+4.11.0=2+\sqrt{25}+4.

其中最短路径经过顶点 bb。

给定陵墓边界以及点 S,TS,T 的位置,请求出从 SS 到 TT 且只在一个边界顶点处穿过陵墓边界的最短路径长度。

输入格式

第一行包含一个整数 nn,表示描述陵墓直方图的顶点数量。保证 nn 为偶数。

第二行包含 nn 个整数 v1,v2,…,vnv_1,v_2,\ldots,v_n,其中 v1=vn=0v_1=v_n=0。这些数依次表示沿直方图上边界从基底线段左端走到右端时,竖直边的 xx 坐标和水平边的 yy 坐标。竖直边和水平边交替出现。每条边长度至少为 11,并且所有 xx 坐标严格递增。

最后一行包含四个整数 sx,sy,tx,tys_x,s_y,t_x,t_y,其中 (sx,sy)(s_x,s_y) 表示点 SS,(tx,ty)(t_x,t_y) 表示点 TT。保证 SS 在直方图外部,TT 在直方图内部,且二者都不在边界上。

输出格式

输出一行一个实数,表示从 SS 到 TT 的最短路径长度。

输出值必须包含整数部分、小数点和小数部分。若你的输出 zz 满足

a−10−3<z<a+10−3,a-10^{-3}<z<a+10^{-3},

其中 aa 为标准答案,则会被判为正确。

两点 p=(x1,y1)p=(x_1,y_1) 和 q=(x2,y2)q=(x_2,y_2) 的欧几里得距离为

(x1−x2)2+(y1−y2)2.\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}.

数据范围

  • 4≤n≤1000004\le n\le 100000;
  • nn 为偶数;
  • v1=vn=0v_1=v_n=0;
  • 0≤vi≤1060\le v_i\le 10^6;
  • −106≤sx,sy≤2⋅106-10^6\le s_x,s_y\le 2\cdot 10^6;
  • 0<tx,ty<1060<t_x,t_y<10^6。

样例 1

输入

12
0 5 2 8 5 3 7 6 11 4 13 0
11 8 3 3

输出

10.077687

样例 2

输入

8
0 7 2 2 5 7 7 0
-2 4 6 4

输出

11.767829

样例 3

输入

4
0 5 8 0
8 6 4 2

输出

6.0