【题解】P3699 [CQOI2017]小Q的草稿

5ab_juruo · 2023-02-25 19:28:31 · 题解

给一种不需要 set 的做法。

考虑数关键点之间的连线与多少个三角形相交。显然线段可以拆成两条射线答案的差，且射线的起点都是关键点。

同时注意到，当射线起点固定时，三角形的限制等价于极角的一段区间，代表这一段答案要加一。

枚举关键点作为射线起点，将所有要求的射线方向和三角形贡献的起点、终点按极角排序，扫描线即可。注意端点也要算进去。如果有跨越 0,2\pi 的贡献，则可以拆成两段来算。

复杂度 \mathcal{O}(n(n+m)\log(n+m))。

const int max_n = 1000, max_m = 1000;

struct point
{
    int x, y;
    friend istream& operator>>(istream& is, point& p)
    {
        is >> p.x >> p.y;
        return is;
    }
    bool operator<(const point& rhs) const
    {
        if ((rhs.x > 0) ^ (x > 0))
            return x < rhs.x;
        return 1ll * y * rhs.x < 1ll * x * rhs.y;
    }
}
p[max_n], a[max_m], b[max_m], c[max_m];
vector<pair<point, int>> qc;
int f[max_n][max_n];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> p[i];
    for (int i = 0; i < m; i++)
        cin >> a[i] >> b[i] >> c[i];
    qc.reserve(n + m * 3);

    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        qc.clear();
        for (int j = 0; j < i; j++)
            qc.emplace_back(point{ 2 * p[i].x - p[j].x, 2 * p[i].y - p[j].y }, j);
        for (int j = i + 1; j < n; j++)
            qc.emplace_back(p[j], j);

        for (int j = 0; j < m; j++)
        {
            point x[3] = { a[j], b[j], c[j] };
            sort(x, x + 3, [&](point lhs, point rhs) {
                return 1ll * (rhs.y - p[i].y) * (lhs.x - p[i].x) > 1ll * (rhs.x - p[i].x) * (lhs.y - p[i].y);
            });
            if (point{ x[0].x - p[i].x, x[0].y - p[i].y } < point{ x[2].x - p[i].x, x[2].y - p[i].y })
            {
                qc.emplace_back(x[0], -1);
                qc.emplace_back(x[2], n);
            }
            else
            {
                qc.emplace_back(point{ p[i].x, int(2e8) }, -1);
                qc.emplace_back(x[2], n);
                qc.emplace_back(x[0], -1);
            }
        }

        for (auto &[pt, _] : qc)
            pt.x -= p[i].x, pt.y -= p[i].y;
        sort(qc.begin(), qc.end());

        int cnt = 0;
        for (auto [_, x] : qc)
        {
            if (x == -1)
                cnt++;
            else if (x == n)
                cnt--;
            else if (x < i)
                ans += (cnt == f[x][i]);
            else
                f[i][x] = cnt;
        }
    }

    cout << ans << endl;

    return 0;
}