Description
Input
Output
Sample Input
3 1 1 1 2 2 2
Sample Output
8.0000
Data Constraint
题解
我还挺喜欢数学的呢 这题一眼看上去不会，化化式子没想到未知数竟然是一个反比例+一次函数的样子。 长这样：
a
x
+
b
x
\frac a x+bx
xa+bx 当时心态就没了。 原来这玩意是一个在高中叫做双勾函数（或对勾函数或耐克函数） 很好，于是我们就看看这个玩意长什么样—— 既然是长这个样子，那么应该就有一个顶点（最小点）。 利用均值不等式可以得到——
(
a
b
a
,
2
a
b
)
(\frac{\sqrt{ab}}a,2\sqrt{ab})
(aab
,2ab
) 由于图中有很多很多的双勾函数，那么其中必然有一些线没有用的。 我们考虑删去这些没有用的
怎么删？ 首先我们对于任意两点——满足
a
i
<
a
j
且
y
i
<
y
j
（
答
案
）
a_i<a_j且y_i<y_j（答案）
ai<aj且yi<yj（答案） 那么
a
i
+
b
i
+
a
i
∗
x
+
b
i
x
<
a
j
+
b
j
+
a
j
∗
x
+
b
j
x
a_i+b_i+a_i*x+\frac{b_i}{x}<a_j+b_j+a_j*x+\frac{b_j}{x}
ai+bi+ai∗x+xbi<aj+bj+aj∗x+xbj 化一波式子得到：
x
>
b
i
−
b
j
a
j
−
a
i
x>\frac{b_i-b_j}{a_j-a_i}
x>aj−aibi−bj 设
c
[
i
,
j
]
=
b
i
−
b
j
a
j
−
a
i
c[i,j]=\frac{b_i-b_j}{a_j-a_i}
c[i,j]=aj−aibi−bj 则我们对于一个
c
[
i
,
j
]
>
c
[
j
,
k
]
c[i,j]>c[j,k]
c[i,j]>c[j,k]那么j这个点就是没有用的。 所以说，我们就得到一个序列
d
d
d，序列满足
c
[
d
i
−
1
,
d
i
]
<
c
[
d
i
,
d
i
+
1
]
c[d_{i-1},d_i]<c[d_i,d_{i+1}]
c[di−1,di]<c[di,di+1] 这个东东是递增的。 那么我们发现：当
x
x
x在
c
[
d
i
−
1
,
d
i
]
c[d_{i-1},d_i]
c[di−1,di]到
c
[
d
i
,
d
i
+
1
]
c[d_i,d_{i+1}]
c[di,di+1]这段区间内时，
d
i
d_i
di的函数值是最大的。 因此，我们在
d
i
d_i
di的函数上判断这段区间的最小值即可。 怎么判断？可能有三种情况： 1、在顶点左边。 2、在顶点右边。 3、横跨顶点。
O
(
n
)
O(n)
O(n)求即可。
代码
var
i
,j
,k
,l
,n
,m
,now
:longint
;
a
,b
,d
:array
[0..1000003] of longint
;
op
,oq
,x
,y
,ans
,aa
,bb
:extended
;
function
min(x
,y
:extended
):extended
;
begin
if x
<y then
exit(x
);exit(y
);
end
;
procedure
qsort(l
,r
:longint
);
var
i
,j
,m
,m1
:longint
;
begin
i
:=l
;j
:=r
;
m
:=a
[(l
+r
) div
2];
m1
:=b
[(l
+r
) div
2];
repeat
while (a
[i
]<m
) or
((a
[i
]=m
) and
(b
[i
]<m1
)) do inc(i
);
while (a
[j
]>m
) or
((a
[j
]=m
) and
(b
[j
]>m1
)) do dec(j
);
if i
<=j then
begin
a
[0]:=a
[i
];a
[i
]:=a
[j
];a
[j
]:=a
[0];
b
[0]:=b
[i
];b
[i
]:=b
[j
];b
[j
]:=b
[0];
inc(i
);dec(j
);
end
;
until i
>j
;
if l
<j then
qsort(l
,j
);
if r
>i then
qsort(i
,r
);
end
;
function
pd(i
:longint
):boolean
;
var
x
,y
,op
,oq
:extended
;
begin
x
:=b
[d
[now
]]-b
[d
[now
-1]];
y
:=a
[d
[now
-1]]-a
[d
[now
]];
op
:=x
/y
;
x
:=b
[i
]-b
[d
[now
]];
y
:=a
[d
[now
]]-a
[i
];
oq
:=x
/y
;
if op
>oq then
exit(true
);
exit(false
);
end
;
begin
readln(n
);
for i
:=1 to n
do
begin
read(a
[i
],b
[i
]);
end
;
qsort(1,n
);
now
:=1;
d
[1]:=1;
for i
:=2 to n
do
begin
if a
[i
]>a
[1] then
begin
inc(now
);
d
[now
]:=i
;
j
:=i
;
break;
end
;
end
;
for i
:=j
+1 to n
do
begin
if a
[i
]>a
[d
[now
]] then
begin
while (now
>=2) and
(pd(i
)) do dec(now
);
inc(now
);d
[now
]:=i
;
end
;
end
;
ans
:=maxlongint
;
for i
:=2 to now
-1 do
begin
x
:=b
[d
[i
]]-b
[d
[i
-1]];
y
:=a
[d
[i
-1]]-a
[d
[i
]];
op
:=x
/y
;
x
:=b
[d
[i
+1]]-b
[d
[i
]];
y
:=a
[d
[i
]]-a
[d
[i
+1]];
oq
:=x
/y
;
aa
:=a
[d
[i
]];
bb
:=b
[d
[i
]];
if op
>sqrt(aa
*bb
)/aa then ans
:=min(ans
,aa
*op
+bb
/op
+aa
+bb
);
if oq
<sqrt(aa
*bb
)/aa then ans
:=min(ans
,aa
*oq
+bb
/oq
+aa
+bb
);
if (op
<=sqrt(aa
*bb
)/aa
) and
(oq
>=sqrt(aa
*bb
)/aa
) then ans
:=min(ans
,2*sqrt(aa
*bb
)+aa
+bb
);
end
;
x
:=b
[d
[now
]]-b
[d
[now
-1]];
y
:=a
[d
[now
-1]]-a
[d
[now
]];
aa
:=a
[d
[now
]];bb
:=b
[d
[now
]];
op
:=x
/y
;
if op
>sqrt(aa
*bb
)/aa then ans
:=min(ans
,aa
*op
+bb
/op
+aa
+bb
)
else ans
:=min(ans
,2*sqrt(aa
*bb
)+aa
+bb
);
writeln(ans
:0:4);
end
.
