「2016122-T3」通技进阶-计算几何

JPY 精进了生物以后准备再去精进一下通技,于是就向通技竞赛(我也不知道是什么)的同学去请教了各种问题。通技竞赛的同学非常耐心,为他解答了各种问题。过了不久，JPY 感觉自己通技可以虐场了。于是通技竞赛的同学就给他出了一个问题:一个三维空间里有 $n$ 条直线,请找出一个直线的集合,使得这个集合里的直线两两有交点。请告诉他这个集合的最大大小。JPY 又瞬间秒掉了这道题，现在他想来考考你，来确认自己是否能真的虐场。

输入

第一行一个整数 $n$,表示直线条数。
下面 $n$ 行,每行 $6$ 个整数表示一条直线,前 $3$ 个整数表示这条直线上的一个点的 $x,y,z$ 坐标，后 $3$ 个整数表示这条直线上的另一个点的 $x,y,z$坐标。

数据保证没有两条直线重合,且没有直线垂直于 $x$ 轴。

输出

一行一个整数，表示集合的最大大小。

题解

我们可以把三维空间上的直线想成二维平面上在一条直线上匀速移动的点。我们可以先算出每个点在 $0s$ 时所在的坐标和每秒的移动速度。
于是我们枚举每个点作为原点,然后找出所有经过原点的点,并先将它们按照经过原点时间排序计算一下答案,再将它们按照极角排序再计算一下答案,最后取 $max$ 就可以了。
时间复杂度 $O ( n^2\log n )$

代码

#include <bits/stdc++.h>
const double eps = 1e-7;
const int MAXN = 2005;
using namespace std;
struct Point {
    double x, y, vx, vy;
} a[MAXN], q;
struct Vector {
    double x, y;
    inline friend bool operator < (const Vector &a, const Vector &b) {
        if (abs(atan2(a.y, a.x) - atan2(b.y, b.x)) < eps) return abs(a.x - b.x) < eps ? a.y < b.y : a.x < b.x;
        return atan2(a.y, a.x) < atan2(b.y, b.x);
    };
} b[MAXN];
inline double det(const Vector &a, const Vector &b) { return a.x * b.y - a.y * b.x; }
double tmp[MAXN];
int ans;
int n, tot;
int main() {
    std::ios::sync_with_stdio(0), std::cin.tie(0), std::cin >> n;
    double x1, y1, x2, y2, t1, t2;
    for (register int i = 1; i <= n; i++) std::cin >> t1 >> x1 >> y1 >> t2 >> x2 >> y2, a[i].vx = (x2 - x1) / (t2 - t1), a[i].vy = (y2 - y1) / (t2 - t1), a[i].x = x1 - a[i].vx * t1, a[i].y = y1 - a[i].vy * t1;
    for (register int i = 1; i <= n; i++) {
        tot = 0;
        for (register int j = 1; j <= n; j++) {
            if (i ^ j) {
                q.x = a[j].x - a[i].x, q.y = a[j].y - a[i].y, q.vx = a[j].vx - a[i].vx, q.vy = a[j].vy - a[i].vy;
                double t = q.vx ? q.x / q.vx : q.y / q.vy;
                if ((abs(q.x - q.vx * t) < eps) && (abs(q.y - q.vy * t) < eps)) tmp[++tot] = t, b[tot].x = q.vx, b[tot].y = q.vy;
            }
        }
        std::sort(tmp + 1, tmp + tot + 1);
        for (register int j = 1, k; j <= tot; j = k) {
            k = j + 1;
            while (k <= tot && abs(tmp[k] - tmp[k - 1]) < eps) k++;
            ans = std::max(ans, k - j);
        }
        std::sort(b + 1, b + tot + 1);
        for (register int j = 1, k, max; j <= tot; j = k) {
            k = j + 1, max = (abs(b[k].x - b[k - 1].x) < eps && abs(b[k].y - b[k - 1].y) < eps);
            while (k <= tot && abs(det(b[k], b[k - 1])) < eps) {
                k++;
                if (k <= tot && abs(b[k].x - b[k - 1].x) < eps && abs(b[k].y - b[k - 1].y) < eps) max++;
            }
            ans = std::max(ans, k - j - max);
        }
    }
    std::cout << ans + 1;
    return 0;
}