【太阳——几何计算】

题目

代码

#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}); //线段进入elses.erase({u.y, -u.id}); //线段退出}int cnt = 0;for (int i = 1; i <= n; i++)if (st[i])cnt++;cout << cnt;
}