题目

代码

#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
using ll = long long;
const int N = 1e5 + 10;
set<PII> s;
bool st[N];
struct node
{
    int x, y, id;
} arr[2 * N];
int main()
{
    int n, X, Y;
    cin >> n >> X >> Y;

    for (int i = 1; i <= n; i++)
    {
        int x, y, l;
        cin >> x >> y >> l;
        arr[i] = {x - X, Y - y, i};
        arr[i + n] = {x - X + l, Y - y, -i}; //以太阳为原点重新建立坐标系，纵坐标取反主要是为了利用set的默认排序
    }

    sort(arr + 1, arr + 1 + 2 * n, [&](node a, node b)
         { return (ll)a.x * b.y < (ll)a.y * b.x; }); //cot值从小到大顺序扫描（逆时针）（就可能范围而言）

    node last = {-1, 0, 0}; //保存当前最大斜率信息
    for (int i = 1; i <= 2 * n; i++)
    {
        auto u = arr[i];
        if (last.y * u.x != u.y * last.x) //若出现新的斜率（发生偏移）
        {
            if (s.size())
                st[s.begin()->second] = 1; //从所有已进入未退出的线段中找出y最大的进行标记
            last = u;
        }

        if (u.id > 0)
            s.insert({u.y, u.id}); //线段进入
        else
            s.erase({u.y, -u.id}); //线段退出
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (st[i])
            cnt++;

    cout << cnt;
}