http://chestnutheng.github.io/tags/%E9%80%86%E5%BA%8F%E5%AF%B9/ Recent content in 逆序对 on 子恒的博客 Hugo zh-CN Wed, 07 Oct 2015 20:33:00 +0800 http://chestnutheng.github.io/reversed_order/ Wed, 07 Oct 2015 20:33:00 +0800 http://chestnutheng.github.io/reversed_order/ <h1 id="逆序对计算的思考tsinghua-ojpa1">逆序对计算的思考(Tsinghua OJ,PA1)</h1> <hr> <p>题目出自清华DSA的Programming Assignment作业灯塔(LightHouse)．</p> <h2 id="描述">描述</h2> <p>海上有许多灯塔，为过路船只照明。</p> <p><img src="http://chestnutheng-blog-1254282572.file.myqcloud.com/c6c8562b88ed7fd518cacf0264ae624f59598ed7.png" alt="图一"></p> <p>如图一所示，每个灯塔都配有一盏探照灯，照亮其东北、西南两个对顶的直角区域。探照灯的功率之大，足以覆盖任何距离。灯塔本身是如此之小，可以假定它们不会彼此遮挡。</p> <p><img src="http://chestnutheng-blog-1254282572.file.myqcloud.com/9d7f16b4bddbee9795e12ba22fd7f88af5438aa6.png" alt="图二"></p> <p>若灯塔A、B均在对方的照亮范围内，则称它们能够照亮彼此。比如在图二的实例中，蓝、红灯塔可照亮彼此，蓝、绿灯塔则不是，红、绿灯塔也不是。<br> 现在，对于任何一组给定的灯塔，请计算出其中有多少对灯塔能够照亮彼此。</p> <h2 id="输入">输入</h2> <p>共n+1行。<br> 第1行为1个整数n，表示灯塔的总数。<br> 第2到n+1行每行包含2个整数x, y，分别表示各灯塔的横、纵坐标。</p> <h2 id="输出">输出</h2> <p>1个整数，表示可照亮彼此的灯塔对的数量。</p> <h2 id="样例">样例</h2> <p>Input:</p> <div class="highlight"><div class="chroma"> <table class="lntable"><tr><td class="lntd"> <pre tabindex="0" class="chroma"><code><span class="lnt">1 </span><span class="lnt">2 </span><span class="lnt">3 </span><span class="lnt">4 </span></code></pre></td> <td class="lntd"> <pre tabindex="0" class="chroma"><code class="language-fallback" data-lang="fallback"><span class="line"><span class="cl">3 </span></span><span class="line"><span class="cl">2 2 </span></span><span class="line"><span class="cl">4 3 </span></span><span class="line"><span class="cl">5 1 </span></span></code></pre></td></tr></table> </div> </div><p>Output:</p> <div class="highlight"><div class="chroma"> <table class="lntable"><tr><td class="lntd"> <pre tabindex="0" class="chroma"><code><span class="lnt">1 </span></code></pre></td> <td class="lntd"> <pre tabindex="0" class="chroma"><code class="language-fallback" data-lang="fallback"><span class="line"><span class="cl">1 </span></span></code></pre></td></tr></table> </div> </div><h2 id="限制">限制</h2> <p>对于90%的测例：1 ≤ n ≤ 3×10^5<br> 对于95%的测例：1 ≤ n ≤ 10^6<br> 全部测例：1 ≤ n ≤ 4×10^6<br> 灯塔的坐标x, y是整数，且不同灯塔的x, y坐标均互异<br> 1 ≤ x, y ≤ 10^8<br> 时间：2 sec<br> 内存：256 MB</p> <h2 id="提示">提示</h2> <p>注意机器中整型变量的范围，C/C++中的int类型通常被编译成32位整数，其范围为[-231, 231 - 1]，不一定足够容纳本题的输出。</p>