题解：P1142 轰炸

白鲟 · 2024-08-29 17:56:00 · 题解

目前题解区仅有两种做法：\operatorname{O}(n^3) 枚举复杂度不优，\operatorname{O}(n^2\log n) 斜率排序精度可能不稳定。

采用基于叉积的极角排序可以兼顾精度和复杂度。具体地，枚举起始点，并算出其余点相对其的向量，对向量进行极角排序，同向的向量会相邻，此时只需要简单统计同向的段的长度即可。

注意事项是同向或反向都是同一直线，因此对于每个起始点，都应当将除自身外所有的点均加入排序（而不应采用 j<i 等排除方法）。由于在每条直线上至少有两个点，使得在这条直线上的其他点对于它来说都在同一方向，上述方法成立。

#include <algorithm>
#include <cstdio>
const int maxn = 700;
struct Vector {
    int x, y;
    Vector(int x = 0, int y = 0) : x(x), y(y){}
    friend int cross(const Vector &t1, const Vector &t2) {
        return t1.x * t2.y - t1.y * t2.x;
    }
    friend bool parallel(const Vector &t1, const Vector &t2) {
        return !cross(t1, t2);
    }
    bool operator<(const Vector &t) {
        return cross(*this, t) > 0;
    }
};
struct Point {
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y){}
    Vector operator-(const Point &t) {
        return {x - t.x, y - t.y};
    }
};
Vector t[maxn + 1];
Point a[maxn + 1];
int ans, now, tot, n;
int main() {
    scanf("%d", &n);
    ans = 2;
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &a[i].x, &a[i].y);
    }
    for (int i = 1; i <= n; ++i) {
        tot = 0;
        for (int j = 1; j <= n; ++j) {
            if (i != j) {
                t[++tot] = a[i] - a[j];
            }
        }
        std::sort(t + 1, t + tot + 1);
        now = 2;
        for (int j = 2; j <= tot; ++j) {
            if (parallel(t[j], t[j - 1])) {
                ++now;
            }
            else {
                now = 2;
            }
            ans = std::max(ans, now);
        }
    }
    printf("%d", ans);
    return 0;
}