4136 - 平面奇景

题目描述

有一个特殊的平面世界,里面所有的物品都处在一个平面内。小胡正在探索这片平面奇景,他看到了一片连绵的山脉,这些山都是等腰直角三角形,所有三角形的斜边都作为山底落在一条直线上。

小胡在记录测量的数据时,想到只要记录下每座山的山顶的坐标( x_i,y_i ),就可以得到整座山的信息。

现在希望你根据小胡记录的这 n 座山的信息,求出被山覆盖的总面积。(这是一个平面世界,所以山与山重叠的部分只要记录一次

输入

第一行为一个整数 n,表示山的数量;

接下来会有 n 行,每行包含两个整数 x_i,y_i,表示第 i 座山山顶的坐标。

输出

输出所有山的可见面积,为保证结果为整数,所以输出面积乘以 4 的结果。

样例

输入

3
1 1
2 1
3 1

输出

10
说明

更多样例

输入

3
1 2
1 3
2 4

输出

64

【样例1解释】


三个山峰有交集,可见面积为&nbsp;<span class="katex math inline" style="font-size:1.21em;line-height:1.2;font-family:KaTeX&#95;Main&#44; &quot;">2.5</span>&nbsp;。

输出结果乘以&nbsp;<span class="katex math inline" style="font-size:1.21em;line-height:1.2;font-family:KaTeX&#95;Main&#44; &quot;">4</span>&nbsp;所以答案是&nbsp;<span class="katex math inline" style="font-size:1.21em;line-height:1.2;font-family:KaTeX&#95;Main&#44; &quot;">10</span>&nbsp;。

【数据范围】

对于&nbsp;<span class="katex math inline" style="font-size:1.21em;line-height:1.2;font-family:KaTeX&#95;Main&#44; &quot;">30</span>&nbsp;% 的数据,<span class="katex math inline" style="font-size:1.21em;line-height:1.2;font-family:KaTeX&#95;Main&#44; &quot;">&nbsp;1 &lt;= n <span style="color:#333333;font-family:KaTeX&#95;Main&#44; &quot;font-size:14.52px;">&lt;=&nbsp;</span>1&#44;000&nbsp;</span>;

对于&nbsp;<span class="katex math inline" style="font-size:1.21em;line-height:1.2;font-family:KaTeX&#95;Main&#44; &quot;">60</span>&nbsp;% 的数据,<span class="katex math inline" style="font-size:1.21em;line-height:1.2;font-family:KaTeX&#95;Main&#44; &quot;">&nbsp;1 <span style="color:#333333;font-family:KaTeX&#95;Main&#44; &quot;font-size:14.52px;">&lt;=&nbsp;</span>n <span style="color:#333333;font-family:KaTeX&#95;Main&#44; &quot;font-size:14.52px;">&lt;=&nbsp;</span>10&#44;000&nbsp;</span>;

对于&nbsp;<span class="katex math inline" style="font-size:1.21em;line-height:1.2;font-family:KaTeX&#95;Main&#44; &quot;">100</span>&nbsp;% 的数据,<span class="katex math inline" style="font-size:1.21em;line-height:1.2;font-family:KaTeX&#95;Main&#44; &quot;">&nbsp;1 <span style="color:#333333;font-family:KaTeX&#95;Main&#44; &quot;font-size:14.52px;">&lt;=&nbsp;</span>n <span style="color:#333333;font-family:KaTeX&#95;Main&#44; &quot;font-size:14.52px;">&lt;=&nbsp;</span>100&#44;000&nbsp;</span>;

<span class="katex math inline" style="font-size:1.21em;line-height:1.2;font-family:KaTeX&#95;Main&#44; &quot;">1 <span style="color:#333333;font-family:KaTeX&#95;Main&#44; &quot;font-size:14.52px;">&lt;=&nbsp;</span>x&#95;i&#44;y&#95;i <span style="color:#333333;font-family:KaTeX&#95;Main&#44; &quot;font-size:14.52px;">&lt;=&nbsp;</span>100&#44;000&#44;000</span>&nbsp;。

来源

23-9-A组月赛

题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过人数 0
金币数量
难度 未标记


上一题 下一题