CF1142C.U2

提高+/省选-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Recently Vasya learned that, given two points with different xx coordinates, you can draw through them exactly one parabola with equation of type y=x2+bx+cy = x^2 + bx + c, where bb and cc are reals. Let's call such a parabola an UU-shaped one.

Vasya drew several distinct points with integer coordinates on a plane and then drew an UU-shaped parabola through each pair of the points that have different xx coordinates. The picture became somewhat messy, but Vasya still wants to count how many of the parabolas drawn don't have any drawn point inside their internal area. Help Vasya.

The internal area of an UU-shaped parabola is the part of the plane that lies strictly above the parabola when the yy axis is directed upwards.

最近,瓦夏了解到:对于横坐标不同的两个点,恰好可以作一条形如 y=x2+bx+cy = x^2 + bx + c 的抛物线(其中 bb 和 cc 为实数)经过这两点。我们称这类抛物线为 U 形抛物线。

瓦夏在平面上画出了若干个互不相同的整数坐标点,然后对每一对横坐标不同的点,都画出了一条经过它们的 U 形抛物线。图画变得有些杂乱,但瓦夏仍希望统计:所画出的所有抛物线中,有多少条的内部区域内不包含任何已画出的点。请你帮助瓦夏。

U 形抛物线的内部区域定义为:当 yy 轴正向朝上时,平面中严格位于该抛物线上方的部分。

输入格式

The first line contains a single integer nn (1≤n≤100 0001 \le n \le 100\,000) — the number of points.

The next nn lines describe the points, the ii-th of them contains two integers xix_i and yiy_i — the coordinates of the ii-th point. It is guaranteed that all points are distinct and that the coordinates do not exceed 10610^6 by absolute value.

第一行包含一个整数 nn(1≤n≤100 0001 \le n \le 100\,000)—— 点的数量。

接下来的 nn 行描述这些点,其中第 ii 行包含两个整数 xix_i 和 yiy_i —— 第 ii 个点的坐标。保证所有点互不相同,且坐标的绝对值不超过 10610^6。

输出格式

In the only line print a single integer — the number of UU-shaped parabolas that pass through at least two of the given points and do not contain any of the given points inside their internal area (excluding the parabola itself).

在唯一的一行中输出一个整数——表示经过给定的至少两个点、且其内部区域(不包括抛物线本身)不包含任何给定点的 UU-形抛物线的数量。

输入输出样例

  • 输入#1

    3
    -1 0
    0 2
    1 0

    输出#1

    2
  • 输入#2

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

    输出#2

    1

说明/提示

On the pictures below all UU-shaped parabolas that pass through at least two given points are drawn for each of the examples. The UU-shaped parabolas that do not have any given point inside their internal area are drawn in red.

The first example.

The second example.

在下面的图片中,针对每个示例,绘制了所有至少经过两个给定点的 UU 形抛物线。其中,内部区域不包含任何给定点的 UU 形抛物线以红色绘制。

第一个示例。

第二个示例。

输入解题思路,AI测评打分。不知道怎么写?

首页