3 条题解
-
1
直接求范围内的点不好求,所以考虑换种思路:求不在范围内的点,用三角形三边所在直线将平面分割

设查询为
红色区域内点集可表示为
黄色区域内点集可表示为
蓝色区域内点集可表示为 (此处涉及高中数学直线一般式,但是可以通过看图理解)
因此,根据容斥定理,可以得出其中单色区域较为好求,排序后双指针或二分均可 对于不同色块的交集,二维数点即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef array<int,4> ARR; typedef pair<int,int> PII; const int N = 1e6 + 5; int n,q,ans[N]; ARR a[N],p[N]; bool cmpx(ARR a,ARR b) { return a[0] < b[0];} bool cmpy(ARR a,ARR b) { return a[1] < b[1];} bool cmpl(ARR a,ARR b) { return a[2] > b[2];} struct BIT { int tr[N]; void add(int x) { for(;x < N;x += x & -x) tr[x] ++; } int ask(int x) { int ans = 0; for(;x;x -= x & -x) ans += tr[x]; return ans; } } tr[3]; void solve() { cin >> n >> q; for(int i = 1;i <= n;i ++) { cin >> a[i][0] >> a[i][1]; a[i][2] = a[i][0] + a[i][1]; } for(int i = 1;i <= q;i ++) { cin >> p[i][0] >> p[i][1] >> p[i][2]; p[i][2] += p[i][0] + p[i][1]; ans[p[i][3] = i] = n; } sort(a + 1,a + n + 1,cmpx); sort(p + 1,p + q + 1,cmpx); for(int i = 1,j = 0;i <= q;i ++) { while(j < n && a[j + 1][0] < p[i][0]) { tr[0].add(a[++ j][1]); } ans[p[i][3]] -= j;// x < X ans[p[i][3]] += tr[0].ask(p[i][1] - 1);// x < X && y < Y } sort(a + 1,a + n + 1,cmpy); sort(p + 1,p + q + 1,cmpy); for(int i = 1,j = 0;i <= q;i ++) { while(j < n && a[j + 1][1] < p[i][1]) j ++; ans[p[i][3]] -= j;// y < Y } sort(a + 1,a + n + 1,cmpl); sort(p + 1,p + q + 1,cmpl); for(int i = 1,j = 0;i <= q;i ++) { while(j < n && a[j + 1][2] > p[i][2]) { j ++; tr[1].add(a[j][0]); tr[2].add(a[j][1]); } ans[p[i][3]] -= j;// x + y > X + Y + D ans[p[i][3]] += tr[1].ask(p[i][0] - 1);// x < X && x + y > X + Y + D ans[p[i][3]] += tr[2].ask(p[i][1] - 1);// y < Y && x + y > X + Y + D } for(int i = 1;i <= q;i ++) { cout << ans[i] << "\n"; } } signed main() { freopen("triangular.in","r",stdin); freopen("triangular.out","w",stdout); ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); int t = 1; // cin >> t; while(t --) solve(); return 0; }
信息
- ID
- 28
- 时间
- 5000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 57
- 已通过
- 7
- 上传者