P6641 题解

船酱魔王 · 2024-09-08 13:25:48 · 题解

题意回顾

平面直角坐标系中，每个在 (x_i,0) 的人都有两条视角直线，两条直线之间画出的无限三角形区域称为这个人的视角。

给定 L,R,Y 和两条直线的斜率，求出有多少个 (i,Y) 被不超过 j 个人的视角包含。

分析

我们只需要关心在 x 轴上的每个人视角在 y=Y 上的投影即可，不难用一次函数知识算出每个投影对应的一段连续区间。我们可以使用前缀和的处理技巧把问题转化为求给定范围内内被 n 个小区间共计覆盖 x 次的整点数量。

可以使用扫描线的技巧，排序所有区间左右端点，对于小区间开始和结束类型的端点进行更新覆盖次数，再把这个端点和下一个之间的部分统计答案。

注意先乘后除而不是使用浮点数，这样可以避免精度误差带来的麻烦，也注意区间开闭的界值是否归属于这个区间的问题。还需要注意最左和最右端点外面的部分，和排序时先左端点后右端点避免在重合的端点之间出现对于负数次数的覆盖统计。

AC 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;
const int N = 1e5 + 5;
int n;
int l, r, y;
pair<int, int> pr[N * 2];
int buc[N];
int main() {
    scanf("%d", &n);
    scanf("%d%d%d", &l, &r, &y);
    int x, v, h;
    for(int i = 1; i <= n; i++) {
        scanf("%d%d%d", &x, &v, &h);
        int al, ar;
        int yh = y * h;
        int xl = x - ((yh % v == 0) ? (yh / v - 1) : (yh / v));
        int xr = x + ((yh % v == 0) ? (yh / v) : (yh / v + 1));
        pr[i * 2 - 1] = (pair<int, int>){xl, -1};
        pr[i * 2] = (pair<int, int>){xr, 1};
    }
    sort(pr + 1, pr + n * 2 + 1);
    for(int i = 1; i <= 2 * n; i++) pr[i].first = min(max(pr[i].first, l), r + 1);
    int now = 0;
    pr[2 * n + 1].first = r + 1;
    buc[0] += pr[1].first - l;
    for(int i = 1; i <= 2 * n; i++) {
        now += -pr[i].second;
        buc[now] += pr[i + 1].first - pr[i].first;
    }
    for(int i = 0; i <= n; i++) printf("%d\n", buc[i]), buc[i + 1] += buc[i];
    return 0;
}