调了 $2h$,发现竟然是一个极其若只的问题
首先太阳肯定是先照到最上面的线段,因此在排序线段时按照 $y$ 降序排序。
其次是,每个线段统一到一根轴上才好打标记,做对比(其实这题好像是不是也可以极角排序),所以考虑把线段按照两个端点和太阳的连线,拓展到 $x$ 轴上。
设太阳坐标为 $X, \ Y$,当前线段的一个坐标为 $x_i, \ y_i$,可以得到直线方程($Ax + By + C = 0$)
$$ (Y - y_i)x - (X - x_i)y + Xy_i - x_iY = 0 \tag{1} $$
-
$X = x_i$,$(1)$ 与 $x$ 轴的交点就是 $x = X$
-
$X \not= x_i$,$(1)$ 与 $x$ 轴的交点就是(令 $y = 0$)$x = \frac{x_iY - Xy_i}{Y - y_i}$
这样就可以得到新的 $n$ 组线段,接下来要做的就是遍历已经用 $y$ 降序排序的线段,每次把一整个线段都打上标记,如果出现未打标记的地方,说明可以照射到。
这里特别注意,线段的长度为 $l$,但是它上面的点会有 $l + 1$ 个(除左端点外,长度每 $+1$ 就多一个点),因此我们 人为规定每个点 $x$ 拥有 $[x, \ x + 1)$ 这条线段(是的我就是这里错的),打标记时只要打在这 $l$ 个点上即可。
不过由于 double
打标记很难受,所以需要离散化。所以更准确的说,上一段中打标记的其实是离散化后端点的离散化值,但仍然遵守 $x$ 拥有 $[x, \ x + 1)$ 的规定。
到这里算法基本完成了,但是还差一点,就是对于这个线段内部点的遍历,可能会有一些已经被打标记的点被一直访问,复杂度可以到 $O(n^2)$,因此考虑用 并查集区间染色 的方式优化,即记录点 $i$ 及其右边最小未染色下标,即 $fa[i]$ 表示 $[i, \ R]$ 中未被打标记的最小下标。
时间复杂度 $O(nlogn)$
#include <bits/stdc++.h>
using LL = long long;
struct DSU {
std::vector<int> f, sz;
DSU() {}
DSU(int n) {
init(n);
}
void init(int n) {
f.resize(n);
std::iota(f.begin(), f.end(), 0);
sz.assign(n, 1);
}
int find(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
int size(int x) {
return sz[find(x)];
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
sz[x] += sz[y];
f[y] = x;
return true;
}
bool same(int x, int y) {
return find(x) == find(y);
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, X, Y;
std::cin >> n >> X >> Y;
struct Seg {
int x, y, l;
Seg() {}
Seg(int _x, int _y, int _l): x(_x), y(_y), l(_l) {}
};
std::vector<Seg> seg;
for (int i = 0; i < n; i += 1) {
int x, y, l;
std::cin >> x >> y >> l;
seg.emplace_back(x, y, l);
}
std::sort(seg.begin(), seg.end(), [&](auto a, auto b) {
return a.y > b.y;
});
std::vector<double> p(2 * n);
for (int i = 0; i < n; i += 1) {
auto [x, y, l] = seg[i];
auto ref = [&](int x, int y) -> double {
if (x == X) {
return x;
}
return (1.0 * x * Y - 1.0 * X * y) / (Y - y);
};
p[i] = ref(x, y);
p[i + n] = ref(x + l, y);
}
auto v = p;
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());
int m = v.size();
std::vector<bool> vis(m);
DSU dsu(m);
int ans = 0;
for (int i = 0; i < n; i += 1) {
auto find = [&](double x) -> int {
return std::lower_bound(v.begin(), v.end(), x) - v.begin();
};
int l = find(p[i]);
int r = find(p[i + n]);
bool ok = false;
for (int j = dsu.find(l); j < r; j = dsu.find(j + 1)) {
if (!vis[j]) {
vis[j] = true;
dsu.merge(j + 1, j);
ok = true;
}
}
ans += ok;
}
std::cout << ans << "\n";
return 0;
}
极角排序
这种思路其实比较符合正常人思维,就是以太阳为原点,把 $n$ 条线段拆成 $2n$ 个点,按照极角(极坐标里的那个角,也就是和 $x$ 轴正向的夹角)排序。
然后从 $(-1, \ 0)$($x$ 轴负向)开始逆时针遍历这些点,并存下所有遍历过且未遇到右端点的那些点的 $y$ 值和对应下标 $id$,记为集合 $S$。
每次从 $S$ 中取出纵坐标 $y$ 最大的点,并对其 $id$ 打上标记,表示可以被照射到。
这样能满足题目条件的原因如下:
-
首先极角排序后,这 $2n$ 个点就根据极角分成了若干份,每一份的极角都相同(在同一射线上),这样就相当于太阳扫过了一遍这些线段
-
其次是每次都是从 $S$ 中取出最大 $y$ 的那个点,这样可以保证同极角的点只取最高点被照射;同时,只要这个最高点没有遇到它的右端点,那就会始终把这条线段的张角内部屏蔽,而只要遇到了右端点,这个点被拿出集合 $S$,此时下面的点就会选一个最高点被照射。这就跟拿手电筒从高处扫地面是一样的。
#include <bits/stdc++.h>
using LL = long long;
struct Point {
int x, y;
constexpr Point(): x{}, y{} {}
constexpr Point(int _x, int _y): x{_x}, y{_y} {}
constexpr void reduce() {
int d = std::gcd(x, y);
if (d != 0) {
x /= d, y /= d;
}
}
constexpr static int area(Point a) {
if (a.x >= 0 and a.y >= 0) {
return 1;
} else if (a.x < 0 and a.y >= 0) {
return 2;
} else if (a.x < 0 and a.y < 0) {
return 3;
}
return 4;
}
constexpr static double angle(Point a) {
return atan2(a.y, a.x);
}
constexpr double angle() {
return angle(*this);
}
constexpr static LL Getd2(Point lhs, Point rhs) { // 两点间距离的平方
int dx = lhs.x - rhs.x;
int dy = lhs.y - rhs.y;
return 1LL * dx * dx + 1LL * dy * dy;
}
constexpr static double Getd(Point lhs, Point rhs) { // 两点间距离
return std::sqrt(Getd2(lhs, rhs));
}
constexpr Point &operator+=(Point rhs) & {
x += rhs.x;
y += rhs.y;
return *this;
}
constexpr Point &operator-=(Point rhs) & {
x -= rhs.x;
y -= rhs.y;
return *this;
}
friend constexpr Point operator+(Point lhs, Point rhs) {
Point res = lhs;
res += rhs;
return res;
}
friend constexpr Point operator-(Point lhs, Point rhs) {
Point res = lhs;
res -= rhs;
return res;
}
friend constexpr Point operator*(Point lhs, int k) {
assert(k == 0);
Point res = lhs;
res.x *= k;
res.y *= k;
return res;
}
constexpr Point operator*=(int k) {
*this = *this * k;
return *this;
}
friend constexpr LL operator*(Point lhs, Point rhs) { // 内积
LL res = 1LL * lhs.x * rhs.x + 1LL * lhs.y * rhs.y;
return res;
}
friend constexpr LL operator^(Point lhs, Point rhs) { // 叉乘
LL res = 1LL * lhs.x * rhs.y - 1LL * lhs.y * rhs.x;
return res;
}
constexpr static LL getd2(Point a) { // 到原点距离的平方
return a * a;
}
constexpr static double getd(Point a) { // 到原点的距离
return std::sqrt(getd2(a));
}
constexpr LL dist2() {
return getd2(*this);
}
constexpr double dist() {
return getd(*this);
}
constexpr LL dist2(int cx, int cy) {
auto c = Point(cx, cy);
return Getd2(*this, c);
}
constexpr double dist(int cx, int cy) {
auto c = Point(cx, cy);
return Getd(*this, c);
}
constexpr LL dist2(Point c) {
return Getd2(*this, c);
}
constexpr double dist(Point c) {
return Getd(*this, c);
}
constexpr LL Area(Point a, Point b, Point c) { // 平行四边形的面积
a -= c;
b -= c;
LL res = a ^ b;
res = res > 0 ? res: -res;
return res;
}
constexpr LL Area(Point b, Point c) {
return Area(*this, b, c);
}
constexpr bool OnSegment(Point c, Point lhs, Point rhs) {
lhs -= c;
rhs -= c;
return (lhs ^ rhs) == 0 and (lhs * rhs) <= 0;
}
constexpr bool OnSegment(Point lhs, Point rhs) {
return OnSegment(*this, lhs, rhs);
}
friend constexpr bool operator<(Point lhs, Point rhs) {
int a1 = area(lhs), a2 = area(rhs);
if (a1 != a2) {
return a1 < a2;
}
LL t = lhs ^ rhs;
if (t != 0) {
return t > 0;
}
return getd2(lhs) < getd2(rhs);
}
friend constexpr bool operator==(Point lhs, Point rhs) {
return lhs.x == rhs.x and lhs.y == rhs.y;
}
friend constexpr bool operator!=(Point lhs, Point rhs) {
return lhs.x != rhs.x or lhs.y != rhs.y;
}
friend std::istream &operator>>(std::istream &is, Point &a) {
return is >> a.x >> a.y;
}
friend std::ostream &operator<<(std::ostream &os, Point &a) {
return os << a.x << " " << a.y;
}
};
struct Node {
Point p;
int id;
Node() {}
Node(Point _p, int _id): p(_p), id(_id) {}
friend bool operator<(Node lhs, Node rhs) {
return lhs.p < rhs.p;
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
Point sun;
std::cin >> sun;
std::vector<Node> v;
for (int i = 0; i < n; i++) {
int x, y, l;
std::cin >> x >> y >> l;
v.emplace_back(Point(x, y) - sun, i);
v.emplace_back(Point(x + l, y) - sun, i + n);
}
std::sort(v.begin(), v.end());
std::vector<bool> vis(n);
std::set<std::pair<int, int>> S;
auto lst = Point(-1, 0);
for (auto [p, id]: v) {
if (p ^ lst) {
if (S.size()) {
vis[S.begin()->second] = true;
}
lst = p;
}
if (id < n) {
S.emplace(-p.y, id);
} else {
S.erase(std::make_pair(-p.y, id - n));
}
}
std::cout << std::accumulate(vis.begin(), vis.end(), 0) << "\n";
return 0;
}
造的一些数据
Input1
2 3 1000000
2 2 2
3 1 2
Output1
2
Input2
10 70 9493997
666 1513 30
365 1513 99
464 1513 79
625 1513 41
863 1513 17
547 1513 78
543 60008 4
75 1513 50
625 27393 41
125 1513 89
Output2
10
Input3
2 0 2000000
0 100000 1900000
0 10000 1910000
Output3
1
Input4
3 5 2000000
1 100000 2
7 100000 2
2 99999 4
Output4
3
Orz,tql