CF1142C.U2
提高+/省选-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Recently Vasya learned that, given two points with different x coordinates, you can draw through them exactly one parabola with equation of type y=x2+bx+c, where b and c are reals. Let's call such a parabola an U-shaped one.
Vasya drew several distinct points with integer coordinates on a plane and then drew an U-shaped parabola through each pair of the points that have different x 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 U-shaped parabola is the part of the plane that lies strictly above the parabola when the y axis is directed upwards.
最近,瓦夏了解到:对于横坐标不同的两个点,恰好可以作一条形如 y=x2+bx+c 的抛物线(其中 b 和 c 为实数)经过这两点。我们称这类抛物线为 U 形抛物线。
瓦夏在平面上画出了若干个互不相同的整数坐标点,然后对每一对横坐标不同的点,都画出了一条经过它们的 U 形抛物线。图画变得有些杂乱,但瓦夏仍希望统计:所画出的所有抛物线中,有多少条的内部区域内不包含任何已画出的点。请你帮助瓦夏。
U 形抛物线的内部区域定义为:当 y 轴正向朝上时,平面中严格位于该抛物线上方的部分。
输入格式
The first line contains a single integer n (1≤n≤100000) — the number of points.
The next n lines describe the points, the i-th of them contains two integers xi and yi — the coordinates of the i-th point. It is guaranteed that all points are distinct and that the coordinates do not exceed 106 by absolute value.
第一行包含一个整数 n(1≤n≤100000)—— 点的数量。
接下来的 n 行描述这些点,其中第 i 行包含两个整数 xi 和 yi —— 第 i 个点的坐标。保证所有点互不相同,且坐标的绝对值不超过 106。
输出格式
In the only line print a single integer — the number of U-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).
在唯一的一行中输出一个整数——表示经过给定的至少两个点、且其内部区域(不包括抛物线本身)不包含任何给定点的 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
说明/提示
On the pictures below all U-shaped parabolas that pass through at least two given points are drawn for each of the examples. The U-shaped parabolas that do not have any given point inside their internal area are drawn in red.
The first example.
The second example.
在下面的图片中,针对每个示例,绘制了所有至少经过两个给定点的 U 形抛物线。其中,内部区域不包含任何给定点的 U 形抛物线以红色绘制。
第一个示例。
第二个示例。
输入解题思路,AI测评打分。不知道怎么写?