← 返回题目列表

Codeforces · 1142/C

C. U2乐队

中文机器翻译题面 查看原题

最近 Vasya 了解到,给定两个具有不同 $$$x$$$ 坐标的点,您可以通过它们精确地绘制一条抛物线,其方程类型为 $$$y = x^2 + bx + c$$$,其中 $$$b$$$ 和 $$$c$$$ 是实数。我们将这样的抛物线称为 $$$U$$$ 形抛物线。

Vasya 在平面上绘制了几个具有整数坐标的不同点,然后通过每对具有不同 $$$x$$$ 坐标的点绘制了 $$$U$$$ 形状的抛物线。图片变得有些混乱,但 Vasya 仍然想计算有多少条绘制的抛物线在其内部区域内没有任何绘制点。帮助瓦夏。

$$$U$$$ 形抛物线的内部区域是当 $$$y$$$ 轴向上时严格位于抛物线上方的平面部分。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100\,000$$$) — 点数。

接下来的 $$$n$$$ 行描述这些点,其中第 $$$i$$$ 包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ — 第 $$$i$$$ 点的坐标。保证所有点都是不同的,并且坐标的绝对值不超过$$$10^6$$$。

输出

在唯一的一行中打印一个整数 - $$$U$$$ 形抛物线的数量,这些抛物线穿过至少两个给定点并且在其内部区域内不包含任何给定点(抛物线本身除外)。

示例

输入 #1

3
-1 0
0 2
1 0

输出 #1

2

输入 #2

5
1 0
1 -1
0 -1
-1 0
-1 -1

输出 #2

1

注意

在下面的图片中,为每个示例绘制了通过至少两个给定点的所有 $$$U$$$ 形抛物线。内部区域内没有任何给定点的 $$$U$$$ 形抛物线用红色绘制。

第一个例子。

第二个例子。