【DSY】直线 题解（平面分块）

Link.

平面分块。

Solution

直接观察题面可以发现，这道题实在没有什么高深的技巧性可言。

于是我们直接暴力：分块。

然后 wjy 大佬表示，这个做法有着二维线段树的思想。

下面阐述一下平面分块。

其实就是对于每个平面，将它直接划分为“田”字型等面积的四个子平面，类似线段树，不断剖分下去，然后固定一个深度。对于一个平面 \(t_o\)，如果当前输入的直线 \(i\) 有可能穿过这个平面，那就把 \(i\) 压入 \(t_o\) 的 vector 里。查询的时候，类线段树查询，找到这个点所在的、最小的子平面，然后依次枚举即可。

在判断“该直线是否会穿过该节点”时，会涉及到一个三个点两两斜率的比较，这个斜率 dp 的实现也涉及到了，转为乘法即可。

最后，这个复杂度级别估着不大，可过。

Code

#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i <= b; ++i)
const int maxn = 1e5 + 5, maxd = 7, inf = 1e9;
int n, q, nw, tot = 1;
double nk, nb;
int X1[maxn], X2[maxn], Y1[maxn], Y2[maxn];
struct node{
	int c[2][2]; vector <int> d;
}t[maxn << 3];
int fx[4][2] = {{1, 0}, {0, 1}, {0, 0}, {1, 1}};

inline void build(int o, int dep, int xl, int xr, int yl, int yr){
	double ny1 = xl * nk + nb, ny2 = xr * nk + nb;
	if((ny1 > yr and ny2 > yr) or (ny1 < yl and ny2 < yl)) return;
	t[o].d.push_back(nw); 
	if(dep == maxd) return;
	rep(i, 0, 3) if(!(t[o].c[fx[i][0]][fx[i][1]])) 
		t[o].c[fx[i][0]][fx[i][1]] = ++tot; 
	int mx = (xl + xr) >> 1, my = (yl + yr) >> 1;
	build(t[o].c[0][0], dep + 1, xl, mx, yl, my), build(t[o].c[0][1], dep + 1, xl, mx, my + 1, yr);
	build(t[o].c[1][0], dep + 1, mx + 1, xr, yl, my), build(t[o].c[1][1], dep + 1, mx + 1, xr, my + 1, yr);
}
inline int qry(int i, int dep, int xl, int xr, int yl, int yr, int x, int y){
	if(!i) return 0;
	if(dep == maxd){ int res = 0;
		for(auto dk : t[i].d) 
			if(1ll * (Y1[dk] - Y2[dk]) * (X1[dk] - x) == 1ll * (Y1[dk] - y) * (X1[dk] - X2[dk])) res += 1;
		return res;
	} int mx = (xl + xr) >> 1, my = (yl + yr) >> 1;
	if(x <= mx and y <= my) return qry(t[i].c[0][0], dep + 1, xl, mx, yl, my, x, y);
	else if(x <= mx) return qry(t[i].c[0][1], dep + 1, xl, mx, my + 1, yr, x, y);
	if(x > mx and y <= my) return qry(t[i].c[1][0], dep + 1, mx + 1, xr, yl, my, x, y);
	else if(x > mx) return qry(t[i].c[1][1], dep + 1, mx + 1, xr, my + 1, yr, x, y);
	return 0;
}

int main(){
	scanf("%d%d", &n, &q);
	rep(i, 1, n){ 
		scanf("%d%d%d%d", &X1[i], &Y1[i], &X2[i], &Y2[i]);
		nk = (double)(Y1[i] - Y2[i]) / (X1[i] - X2[i]), nb = Y1[i] - nk * X1[i], nw = i;
		build(1, 1, 1, inf, 1, inf);
	} while(q--){ int x, y;
		scanf("%d%d", &x, &y);
		printf("%d\n", qry(1, 1, 1, inf, 1, inf, x, y));
	} return 0;
}

RP++;