題目鏈接

??UVa11607 Cutting Cakes

題意

??平面上有n（n≤1 500）個點，其中沒有3 點共線。另外有m（m≤700 000）條直線，你的任務是對于每條直線，輸出3 個數p, q, r，其中p 和q 為該直線兩側的點數（p≤q），r 是直線穿過的點數。

分析

??本題限時6s，還是比較寬松的，直接用分塊法能通過，比如把 n 個點集分成 $8\times 8$ 塊。
??其次，可以構建四叉樹求解。先取 $mid=n/2$ 處的點 p，根據其坐標得到劃分軸，再遍歷所有點 t 進行劃分，t 在坐標軸上則存到當前結點數據中，不在坐標軸上則按照其所在象限存入四棵子樹的數據中并遞歸構建子樹。此后只需要從根結點遞歸查詢：先求根結點數據的首個點與直線兩端點形成的三角形有向面積 s（$s>0$ 則 ++p；$s=0$ 則 ++r；$s<0$ 則 ++q），其它數據點也都求有向面積后進行 p、q、r 進行統計。然后可以利用首個點的有向面積 s 分類討論四個子結點的計數：s = 0 時，左上象限子結點內的數據全部統計給 p，右下象限子結點內的數據全部統計給 q，然后左下、右上兩個象限的子結點進行遞歸查詢；s > 0 時，左上象限子結點內的數據全部統計給 p，然后左下、右下、右上三個象限的子結點進行遞歸查詢；s < 0 時右下象限子結點內的數據全部統計給 q，然后左下、左上、右上三個象限的子結點進行遞歸查詢。

AC 代碼

#include <iostream>
#include <algorithm>
using namespace std;#define M 10000
#define N 1510
#define B 8
int x[N], y[N], u[N], v[N], x1, y1, x2, y2, dx1, dy1, dx2, dy2, vx, vy, a, b, m, n, p, r, kase = 0;int cross(int x1, int y1, int x2, int y2) {return x1*y2 - x2*y1;
}struct {int b[N], bx1, by1, bx2, by2, by4, c;void add(int i) {b[c++] = i;if (c == 1) bx1 = bx2 =x[i], by1 = by2 = y[i];else bx1 = min(bx1, x[i]), bx2 = max(bx2, x[i]), by1 = min(by1, y[i]), by2 = max(by2, y[i]);}void query() {int cc = cross(vx, vy, bx1 - x1, by1 - y1); bool e = cc < 0, f = cc == 0, g = cc > 0;cc = cross(vx, vy, bx2 - x1, by1 - y1); e = e || cc < 0; f = f || cc == 0; g = g || cc > 0;cc = cross(vx, vy, bx1 - x1, by2 - y1); e = e || cc < 0; f = f || cc == 0; g = g || cc > 0;cc = cross(vx, vy, bx2 - x1, by2 - y1); e = e || cc < 0; f = f || cc == 0; g = g || cc > 0;if (f || (e && g)) {for (int i=0; i<c; ++i) {cc = cross(vx, vy, x[b[i]]-x1, y[b[i]]-y1);if (cc > 0) ++p;else if (cc == 0) ++r;}} else if (g) p += c;}
} s[B][B];void query() {x1 = (x1 + dx1) % M; y1 = (y1 + dy1) % M; x2 = (x2 + dx2) % M; y2 = (y2 + dy2) % M;if (x1 == x2 && y1 == y2) y2 = (y1 + 1) % M;p = 0; r = 0; vx = x2 - x1; vy = y2 - y1;for (int i=0; i<B; ++i) for (int j=0; j<B; ++j) s[i][j].query();cout << min(p, n-r-p) << ' ' << max(p, n-r-p) << ' ' << r << endl;
}void solve() {cin >> n;for (int i=0; i<n; ++i) cin >> x[i] >> y[i], u[i] = x[i], v[i] = x[i];sort(u, u+n); sort(v, v+n); a = unique(u, u+n) - u; b = unique(v, v+n) - v;for (int i=0; i<B; ++i) for (int j=0; j<B; ++j) s[i][j].c = 0;for (int i=0, j=(a+B-1)/B, k=(b+B-1)/B; i<n; ++i)s[(lower_bound(u, u+a, x[i]) - u) / j][(lower_bound(v, v+b, y[i]) - v) / k].add(i);cout << "Case #" << ++kase << ':' << endl;cin >> m >> x1 >> y1 >> x2 >> y2 >> dx1 >> dy1 >> dx2 >> dy2;while (m--) query();
}int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int t; cin >> t;while (t--) solve();return 0;
}