No.343 手抜き工事のプロ
問題文
建設業を営むあなたは、喜間市の市政 $N$ 周年を記念したモニュメントの、設計の確認と施工を依頼されました。
そのモニュメントは、縦100cm、横 $L$ cm、高さ1cmの直方体の鋼材を、水平な土台の上に、各鋼材の横方向を南北に向けて、鉛直方向に $N$ 枚重ねたタワー状の構造をしており、さらに、下から $i$ 番目 $(2 \leq i \leq N)$ の鋼材は、1番下の鋼材の位置を基準として、北に $X_i$ cmだけずれた位置に配置されます($X_i$ が負のときは南へ $|X_i|$ cmだけずれる)。
倒壊を防ぐため、各鋼材間を溶接しないといけないのですが、技術的な都合により、各鋼材間の接触面積が100cm$^2$以上でないとうまく溶接することができません。
この要請を満たしていなかった場合は、依頼者に設計が破綻していることを伝えてください。
設計に問題がなければ、あなたは各鋼材間 $N-1$ 箇所の溶接を行うことになっています(なお、一番下の鋼材だけは既に土台にしっかりと固定されているので、土台との間を溶接する必要はありません)。
ところで、あなたは手抜き工事のプロフェッショナルでもあります。
あなたは、各 $i \ (1 \leq i \leq N-1)$ について、下から $i$ 番目の鋼材よりも上にある鋼材全体の重心点を通る鉛直線が、下から $i$ 番目の鋼材と $i+1$ 番目の鋼材の両方(の内部)を貫く場合は、下から $i$ 番目の鋼材と $i+1$ 番目の鋼材の間を溶接しなくても、直ちには倒壊しないことに気付きました。
ただし、鉛直線が(少なくともどちらか一方の)鋼材のちょうど表面を通る場合は、溶接しておかないと不安定になり、直ぐにでも倒壊してしまいそうになるので、溶接が必要です。
モニュメントを直ちには倒壊しないようにするために、あなたは最低でも何箇所を溶接する必要があるでしょうか?
ただし、鋼材は密度の一様な剛体(変形しない物体)とみなせるものとし、溶接することによる形状や質量、密度分布の変化も無視できるものとします。
また、溶接した鋼材同士は、1つの剛体とみなせる(大きな力がかかっても分離しない)ものとします。
入力
$N$ $L$ $X_2$ $X_3$ $\vdots$ $X_N$
$N$, $L$, $X_i \ (2 \leq i \leq N)$ は整数で、
$1 \leq N \leq 10^5$
$1 \leq L \leq 10^4$
$|X_i| \leq 5 \times 10^3$
を満たす。
出力
溶接が必要な箇所数(設計が破綻していたら-1)を出力して改行する。
サンプル
サンプル1
入力
1 6
出力
0
(右側が北、■が鋼材、□は空間)
■■■■■■
そもそも溶接を依頼されていませんね……。
サンプル2
入力
4 2 -1 0 1
出力
3
□□■■
□■■□
■■□□
□■■□
3箇所全てに溶接が必要です。
サンプル3
入力
2 4 4
出力
-1
□□□□■■■■
■■■■□□□□
設計が破綻しています。
サンプル4
入力
3 5 -3 -1
出力
0
□□■■■■■□
■■■■■□□□
□□□■■■■■
手抜き工事チャンス!
サンプル5
入力
5 100 13 29 54 103
出力
0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。