题解 P4623 【[COCI2012-2013#6] BUREK】

ModestCoder_ · 2020-10-25 17:56:27 · 题解

直线能穿过三角形，因为直线是平行于坐标轴的，所以很简单

以x=p为例

若直线能穿过某一个三角形，那么这条直线必定能穿过三角形的某一条边

换句话说，令三角形三个点中横坐标最小是xmin，最大是xmax

如果xmin<p<xmax，直线就能穿过这个三角形

所以可以直接差分，d_{xmin+1}++,d_{xmax}--

然后我傻傻的写了树状数组，不过也好，还能支持动态修改

Code：

#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;
int n, tree1[maxn << 1], tree2[maxn << 1];

inline int read(){
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
    return s * w;
}

int lowbit(int x){ return x & -x; }
void update1(int x, int y){ for (; x < maxn; x += lowbit(x)) tree1[x] += y; }
void update2(int x, int y){ for (; x < maxn; x += lowbit(x)) tree2[x] += y; }
int query1(int x){ int s = 0; for (; x; x -= lowbit(x)) s += tree1[x]; return s; }
int query2(int x){ int s = 0; for (; x; x -= lowbit(x)) s += tree2[x]; return s; }

int main(){
    freopen("buerk.in", "r", stdin);
    freopen("buerk.out", "w", stdout);
    n = read();
    for (int i = 1; i <= n; ++i){
        int xmax = 0, xmin = maxn - 1, ymax = 0, ymin = maxn - 1;
        int x = read(), y = read();
        xmax = max(xmax, x), xmin = min(xmin, x), ymax = max(ymax, y), ymin = min(ymin, y);
        x = read(), y = read();
        xmax = max(xmax, x), xmin = min(xmin, x), ymax = max(ymax, y), ymin = min(ymin, y);
        x = read(), y = read();
        xmax = max(xmax, x), xmin = min(xmin, x), ymax = max(ymax, y), ymin = min(ymin, y);
        update1(xmin + 1, 1), update1(xmax, -1), update2(ymin + 1, 1), update2(ymax, -1);
    }
    int m = read();
    while (m--){
        char c = getchar();
        for (; c != 'x' && c != 'y'; c = getchar());
        int x = read();
        if (c == 'x') printf("%d\n", query1(x));
        else printf("%d\n", query2(x));
    }
    return 0;
}