A1499题解

问题分析
核心需求：判断一条垂直直线 x=c或水平直线 y=c是否能真正分割一个三角形（分割后两部分面积都 > 0）。
关键结论：
1.垂直分割 x=c：三角形被真正分割 ⇨ 三角形的最小 x 坐标 < c < 最大 x 坐标
2.水平分割 y=c：三角形被真正分割 ⇨ 三角形的最小 y 坐标 < c < 最大 y 坐标
（证明：若三角形 x 范围是 [minx, maxx]，直线 x=c 在区间内部，必然穿过三角形内部，分割出两个非零面积区域）
解题思路
1.预处理每个三角形：计算min_x, max_x, min_y, max_y
2.把所有三角形的min_x/max_x存入两个数组，min_y/may_y存入两个数组
3.对这四个数组排序
4.对于每个查询：
x=c：答案 = 总三角形数 - (min_x>= c 的数量) - (max_x <= c 的数量)
y=c：答案 = 总三角形数 - (min_y>= c 的数量) - (max_y <= c 的数量)
5.用二分查找快速统计数量，时间复杂度 O (NlogN + MlogN)，完美适配 N,M=1e5

c++nb666
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
const int MAXN = 1e5 + 5;
vector<int> min_x, max_x;
vector<int> min_y, max_y;
int n, m;
int count_ge(vector<int>& arr, int val) {
    auto it = lower_bound(arr.begin(), arr.end(), val);
    return arr.end() - it;
}
int count_le(vector<int>& arr, int val) {
    auto it = upper_bound(arr.begin(), arr.end(), val);
    return it - arr.begin();
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int x1, y1, x2, y2, x3, y3;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
        int mx = min({x1, x2, x3});
        int Mx = max({x1, x2, x3});
        min_x.push_back(mx);
        max_x.push_back(Mx);
        int my = min({y1, y2, y3});
        int My = max({y1, y2, y3});
        min_y.push_back(my);
        max_y.push_back(My);
    }
    sort(min_x.begin(), min_x.end());
    sort(max_x.begin(), max_x.end());
    sort(min_y.begin(), min_y.end());
    sort(max_y.begin(), max_y.end());
    cin >> m;
    while (m--) {
        string op, eq;
        int c;
        cin >> op >> eq >> c;
        int ans;
        if (op == "x") {
            int bad1 = count_ge(min_x, c);
            int bad2 = count_le(max_x, c);
            ans = n - bad1 - bad2;
        } else {
            int bad1 = count_ge(min_y, c);
            int bad2 = count_le(max_y, c);
            ans = n - bad1 - bad2;
        }
        cout << ans << '\n';
    }
    return 0;
}