题目链接:Codeforces 1143F
最近 Vasya 学会了对于两个 $x$ 坐标不同的点,你可以通过他们画恰好一个类型为 $y = x ^ 2 + bx + c$ 的抛物线,其中 $b$ 和 $c$ 是实数。我们将这样的抛物线叫做 $U$ 形抛物线。
Vasya 在平面上绘制了 $n$ 个不同的点,然后对于每一对 $x$ 坐标不同的点绘制一个 $U$ 形抛物线。Vasya 想计算出有多少条抛物线满足其内部没有其他绘制的点。
我们定义 $U$ 形抛物线的内部区域是严格位于其上方的部分平面。
数据范围:$1\le n \le 10 ^ 5$,$\vert x_i\vert, \vert y_i\vert \le 10 ^ 6$。
Solution
我们每个点的坐标转化为 $(x, y - x ^ 2)$,函数转化为 $y - x ^ 2 = bx + c$。这样通过每一对点的抛物线转化为了直线,问题转化为:有多少条直线满足其严格上方没有其他点。
到此为止问题已经很显然了,我们只需要求出 $n$ 个点的上凸包的线段数量(也就是点数减一)就是答案了。
时间复杂度:$\mathcal O(n\log n)$。
Code
#include <cstdio>
#include <algorithm>
const int N = 1e5 + 5;
int n, st[N];
template <typename Tp> struct Point {
Tp x, y;
Point(Tp _x = 0, Tp _y = 0) {
x = _x, y = _y;
}
bool operator<(const Point &b) const {
return x == b.x ? y > b.y : x < b.x;
}
Point operator+(const Point &b) const {
return Point(x + b.x, y + b.y);
}
Point operator-(const Point &b) const {
return Point(x - b.x, y - b.y);
}
Tp operator*(const Point &b) const {
return x * b.x + y * b.y;
}
Tp operator^(const Point &b) const {
return x * b.y - y * b.x;
}
};
Point<long long> a[N];
template <typename Tp> Tp cross(Point<Tp> a, Point<Tp> b, Point<Tp> x) {
return (x - a) ^ (x - b);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld%lld", &a[i].x, &a[i].y);
a[i].y -= a[i].x * a[i].x;
}
std::sort(a + 1, a + n + 1);
int tp;
st[tp = 1] = 1;
for (int i = 2; i <= n; i++) {
if (a[i].x == a[i - 1].x) continue;
while (tp > 1 && cross(a[st[tp - 1]], a[st[tp]], a[i]) >= 0) tp--;
st[++tp] = i;
}
printf("%d\n", tp - 1);
return 0;
}