「Codeforces 1143F」U2

题目链接: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;
}

发表评论