本文共 6448 字，大约阅读时间需要 21 分钟。
一条直线将平面分为两部分，其中一半的平面称为半平面。多个半平面的交集被称为半平面交。这个交集可能是凸多边形、无限延伸的平面、直线、线段或单个点等。一般来说，我们规定直线的左侧为所需的半平面，以便区分左右两侧。直线应具有方向性，以便区分左右。
#include#include #include #include #include #include #include using namespace std;#define rg registerinline int read() { rg int x = 0, fh = 1; rg char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') fh = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x < 1) ? (x < 3 ? x : x + 3) : x * 10 + (ch - '0'); ch = getchar(); } return x * fh;}const int maxn = 3e5 + 5;long double eps = 1e-16, INF = 1e12;int dcmp(long double now) { return (std::fabs(now) <= eps) ? 0 : (now > 0 ? 1 : -1);}struct Node { long double x, y; Node() {} Node(long double aa, long double bb) : x(aa), y(bb) {} friend Node operator - (const Node& A, const Node& B) { return Node(A.x - B.x, A.y - B.y); } friend Node operator + (const Node& A, const Node& B) { return Node(A.x + B.x, A.y + B.y); } friend Node operator * (const Node& A, long double B) { return Node(A.x * B, A.y * B); } friend Node operator / (const Node& A, long double B) { return Node(A.x / B, A.y / B); } friend long double operator * (const Node& A, const Node& B) { return A.x * B.x + A.y * B.y; } friend long double operator ^ (const Node& A, const Node& B) { return A.x * B.y - A.y * B.x; } friend bool operator == (const Node& A, const Node& B) { return dcmp(A.x - B.x) == 0 && dcmp(A.y - B.y) == 0; } long double angle() { return atan2(y, x); }};long double eps = 1e-12;int main() { // 读取输入并处理 // ... // 算法实现 // ... return 0;}
设抛物线的解析式为 (y = ax^2 + bx)。对于每一条线段，都必须满足：[ y_{i1} \leq ax_i^2 + bx_i \leq y_{i2} ]即：[ ax_i^2 + bx_i - y_{i1} \geq 0 ][ ax_i^2 + bx_i - y_{i2} \leq 0 ]将 (a, b) 分别看作 (x, y) 就是一个半平面的形式。通过二分法确定第几关后，判断是否存在半平面交即可。
#include#include #include #include #include #include #include using namespace std;#define rg registerinline int read() { rg int x = 0, fh = 1; rg char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') fh = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x < 1) ? (x < 3 ? x : x + 3) : x * 10 + (ch - '0'); ch = getchar(); } return x * fh;}const int maxn = 3e5 + 5;const long double eps = 1e-16;const long double INF = 1e12;int dcmp(long double now) { return (std::fabs(now) <= eps) ? 0 : (now > 0 ? 1 : -1);}struct Node { long double x, y; Node() {} Node(long double aa, long double bb) : x(aa), y(bb) {} friend Node operator - (const Node& A, const Node& B) { return Node(A.x - B.x, A.y - B.y); } friend Node operator + (const Node& A, const Node& B) { return Node(A.x + B.x, A.y + B.y); } friend Node operator * (const Node& A, long double B) { return Node(A.x * B, A.y * B); } friend Node operator / (const Node& A, long double B) { return Node(A.x / B, A.y / B); } friend long double operator * (const Node& A, const Node& B) { return A.x * B.x + A.y * B.y; } friend long double operator ^ (const Node& A, const Node& B) { return A.x * B.y - A.y * B.x; } friend bool operator == (const Node& A, const Node& B) { return dcmp(A.x - B.x) == 0 && dcmp(A.y - B.y) == 0; } long double angle() { return atan2(y, x); }};long double eps = 1e-12;int main() { int n = read(); if (n <= 10) { long double eps = 1e-14; rg int aa, bb, cc; for (rg int i = 1; i <= n; ++i) { aa = read(); bb = read(); cc = read(); // 生成直线 struct Line { Node s, t; int id; long double ang; Line(Node A = Node(), Node B = Node(), int C = 0) : s(A), t(B), ang((B - A).angle()), id(C) {} friend bool operator < (const Line& A, const Line& B) { long double r = A.ang - B.ang; if (dcmp(r) != 0) return dcmp(r) == -1; return dcmp((A.t - A.s) ^ (B.t - A.s)) == -1; } friend long double operator * (const Line& A, const Line& B) { return (A.t - A.s) ^ (B.t - B.s); } }; sta[++tp] = Line(Node(-INF, INF), Node(-INF, eps), 0); // 生成交点 // ... } // 进行二分法确定 // ... printf("%d\n", r); return 0; } return 0;}
设三个项目路程的长度分别为 (a, b, c)。如果 (i) 想要获胜，必须满足对于任意的 (j) 都有：[ \frac{a}{v_i} + \frac{b}{u_i} + \frac{c}{w_i} < \frac{a}{v_j} + \frac{b}{u_j} + \frac{c}{w_j} ]这里涉及三个未知数 (a, b, c)，处理起来较为复杂。但如果 (a, b, c) 满足特定条件，(2a, 2b, 2c) 也会满足条件。因此，可以设 (c = 1 - a - b)，从而得到一个半平面交的形式。
此外，还需满足 (x > 0, y > 0, x + y < 1)，并处理 (j) 三个项目速度的特殊情况。为了防止精度问题，系数乘以一个基数 (bas)。
#include#include #include #include #include #include #include using namespace std;#define rg registerinline int read() { rg int x = 0, fh = 1; rg char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') fh = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x < 1) ? (x < 3 ? x : x + 3) : x * 10 + (ch - '0'); ch = getchar(); } return x * fh;}const int maxn = 205;const long double eps = 1e-12;const long double INF = 1e10;const long double bas = 1e5;int dcmp(long double now) { return (std::fabs(now) <= eps) ? 0 : (now > 0 ? 1 : -1);}struct Node { long double x, y; Node() {} Node(long double aa, long double bb) : x(aa), y(bb) {} friend Node operator - (const Node& A, const Node& B) { return Node(A.x - B.x, A.y - B.y); } friend Node operator + (const Node& A, const Node& B) { return Node(A.x + B.x, A.y + B.y); } friend Node operator * (const Node& A, long double B) { return Node(A.x * B, A.y * B); } friend Node operator / (const Node& A, long double B) { return Node(A.x / B, A.y / B); } friend long double operator * (const Node& A, const Node& B) { return A.x * B.x + A.y * B.y; } friend long double operator ^ (const Node& A, const Node& B) { return A.x * B.y - A.y * B.x; } friend bool operator == (const Node& A, const Node& B) { return dcmp(A.x - B.x) == 0 && dcmp(A.y - B.y) == 0; } long double angle() { return atan2(y, x); }};long double eps = 1e-12;int main() { int n = read(); for (rg int i = 1; i <= n; ++i) { // 读取输入并生成直线 // ... } // 进行半平面交计算 // ... if (jud) { if (SI() == 0) jud = 0; } if (jud) { printf("Yes\n"); } else { printf("No\n"); } return 0;}
对于两个亲戚，它们的监视范围分界线是他们两点之间的中垂线。如果跨过这条线，则会被多个亲戚监视。因此，我们可以在边界相邻的亲戚之间建立权重为 1 的边，然后运行最短路径算法。起点是最初监视小杨的亲戚。关键在于如何确定哪两个亲戚的边界是相邻的。
由于 (n) 的范围较小，可以对每个亲戚运行半平面交算法，求出他们与其他亲戚连线的中垂线，并标记它们所属的亲戚ID。将所有中垂线一起运行半平面交，最后与剩下的直线表示的亲戚连边即可。
转载地址：http://rwvyz.baihongyu.com/