1. 点线的基本结构定义
#define x first
#define y second
const int INF = 1e9 + 7;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
struct Line {
double k, b;
};
Line create(int x1, int y1, int x2, int y2) {
int dy = y1 - y2, dx = x1 - x2;
if (dx == 0) return {INF, x1 * 1.0};
double k = dy * 1.0 / dx;
return {k, y1 - k * x1};
}
2. 线段交点
PDD get(Line &l1, Line &l2) {
if (l1.k == l2.k) {
return {INF, INF};
} else if (l1.k == INF) {
return {l1.b, l2.k * l1.b + l2.b};
} else if (l2.k == INF) {
return {l2.b, l1.k * l2.b + l1.b};
}
double xx = (l2.b - l1.b) / (l1.k - l2.k);
return {xx, l1.k * xx + l1.b};
}
3. 平面分割
- 对于 n 条直线，最多能将平面分割为 1+1+2+3+...+n=2n∗(n+1)+1 个部分。
- 对于前 m 条直线，已经将平面分割为 k 个部分，用一个集合保存不重复的直线。则对于新增加的一条直线，若与之前的直线有重合，则其不会对平面的分割有所贡献，直接舍去；而对于之前的所有直线都不会重合，则判断其与之前不重合直线的交点数量（统计不重合交点），则新加入的直线对平面划分的贡献为该直线与之前直线产生的不重合交点的个数+1。
