class="markdown_views prism-github-gist">

链接

http://codeforces.com/contest/996/problem/E

题目大意

给你n" role="presentation">n$n$个向量，长度都小于106" role="presentation">106${10}^6$，让你确定每个向量的符号，使得他们最后加起来长度小于1.5×106" role="presentation">1.5×106$1.5\times {10}^6$

算法雏形

网上都是什么随机化+贪心，太玄学了，虽然也不错，但我还是喜欢非玄学算法。
三个向量分成一组，每个向量取正负就能变成两个向量；六个向量中选出两个向量，最小夹角满足θ∈[0,60∘]" role="presentation">θ∈[0,60∘]$\theta \in [0,{60}^{\circ }]$，假设拥有最小夹角的两个向量为x→,y→" role="presentation">x⃗ ,y⃗ $\overrightarrow{x},\overrightarrow{y}$，那么|x→|,|y→|≤106" role="presentation">|x⃗ |,|y⃗ |≤106$|\overrightarrow{x}|,|\overrightarrow{y}|\le {10}^6$，
|x→−y→|=|x→|2+|y→|2−2|x→||y→|cosθ" role="presentation">|x⃗ −y⃗ |=|x⃗ |2+|y⃗ |2−2|x⃗ ||y⃗ |cosθ−−−−−−−−−−−−−−−−−−√$$|\overrightarrow{x}-\overrightarrow{y}|=\sqrt{|\overrightarrow{x}{|}^2+|\overrightarrow{y}{|}^2-2|\overrightarrow{x}||\overrightarrow{y}|cos\theta }$$，
cosθ∈[12,1]" role="presentation">cosθ∈[12,1]$$cos\theta \in [\frac{1}{2},1]$$
−2|x→||y→|cosθ∈[−2|x→||y→|,−|x→||y→|]" role="presentation">−2|x⃗ ||y⃗ |cosθ∈[−2|x⃗ ||y⃗ |,−|x⃗ ||y⃗ |]$$-2|\overrightarrow{x}||\overrightarrow{y}|cos\theta \in [-2|\overrightarrow{x}||\overrightarrow{y}|,-|\overrightarrow{x}||\overrightarrow{y}|]$$
|x→−y→|∈[|x→|2+|y→|2−2|x→||y→|,|x→|2+|y→|2−|x→||y→| ]" role="presentation">|x⃗ −y⃗ |∈[|x⃗ |2+|y⃗ |2