题解 | #C: Grab the Seat!#题解

题目大意

二维平面，屏幕是 $(0,1)\mathrm{–}(0,m)(0,\; 1)–(0,\; m)$ 的线段,有$nn$行$mm$列座位在屏幕前面，是坐标范围 $1\le x\le n,1\le y\le m1\; \le \; x\; \le \; n,\; 1\; \le \; y\; \le \; m$的整点。有$kk$个座位已经有人，求出到屏幕的视线不被任何人挡住的座位数量。 题目链接 一个人挡住的区域是它与屏幕两端连线所形成的夹角区域。

可见视线遮挡是被两条线段确定的，但是实际上，单条连线也能够确定视线遮挡的范围。,对于一条线，水平向右的直线和它自身形成的夹角，是一定被视线遮挡的，而两条线确定的，刚好就是这两个相邻区域的并集。

对于当前行，能够覆盖该行的，通过左下角的线，一定是在该行以下，而此时显然斜率越大的线，覆盖的越多。!

所以我们逐行处理的时候，保存斜率最大的直线。

对于左下角的直线$y=\frac{i-1}{x_{now}}\ast x+1,x=\frac{x_{now}-1}{y-1}y\; =\; \backslash frac\{i\; -\; 1\}\{x\_\{now\}\}\; *\; x\; +\; 1,\; x\; =\; \backslash frac\{x\_\{now\}-1\}\{y-1\}$。

$x_{now}x\_\{now\}$表示斜率最大的线来在第$nownow$行，且$xx$坐标为$x_{now}x\_\{now\}$。

代码中在分子又额外减一是为了防止结果刚好在整数点上，导致计算错误，因为这个点实际上也是被遮挡的。

右上角的线也同理

我们计算每一行没被覆盖的点。然后计算出左上，左下的线分别的结果。然后取min即可。

代码

#include <cstdio>
#include <iostream>
using namespace std;

const int maxN = 2e5 + 7;

int n, m, k, q, x[maxN], y[maxN], minY[maxN], con[maxN][2];

int main()
{
    scanf("%d%d%d%d", &n, &m, &k, &q);
    for(int i = 1; i <= k; ++i) 
        scanf("%d%d", &x[i], &y[i]);
    while(q--) {
        int num; scanf("%d", &num);
        scanf("%d%d", &x[num], &y[num]);
        for(int i = 1; i <= m; ++i)
            minY[i] = n + 1;
        for(int i = 1; i <= k; ++i)
            minY[y[i]] = min(minY[y[i]], x[i]);
        int now = 1; con[1][0] = minY[1] - 1;
        for(int i = 2; i <= m; ++i) {
            if((long long) (now - 1) * minY[i] < (long long) (i - 1) * minY[now]) 
                now = i;
            con[i][0] =  ((long long) (i - 1) * minY[now] - 1) / (now - 1);
        }
        now = m; con[m][1] = minY[m] - 1;   
        for(int i = m - 1; i >= 1; --i) {
            if((long long) (m - now) * minY[i] < (long long) (m - i) * minY[now])
                now = i;
            con[i][1] = ((long long) (m - i) * minY[now] - 1) / (m - now);
        }
        long long ans = 0;
        for(int i = 1; i <= m; ++i)
            ans += min(con[i][0], con[i][1]);
        printf("%lld\n", ans);
    }
    return 0;
}