1 条题解

  • 0
    @ 2025-5-5 20:44:19

    题意分析

    给定 $n$ 个平面点,找出一条包含最多共线点的直线。如果该直线上的点数 $\ge 4$,则认为这些点属于火车车窗,应删除它们,反之不删除任何点。输出被删除的点数。


    解题思路

    1. 对于每个点 $i$,将它与其它点 $j$ 的连线斜率 $k$ 记录下来,斜率定义为

      $$ k = \begin{cases} \infty, & x_j = x_i;\\ \displaystyle\frac{y_j - y_i}{x_j - x_i}, & \text{其他}. \end{cases} $$
    2. 对每个 $i$,对该点到其他点的所有 $k$ 值排序,统计相同斜率的连续段长度,记最大值为 $m_i$。该点参与的最大共线点数为 $m_i + 1$(包括其自身)。

    3. 枚举所有 $i$,取全局最大 $M = \max_i(m_i + 1)$。如果 $M<4$,输出 0;否则输出 $M$。


    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    const double EPS = 1e-8;
    const double INF = 1e20;
    
    struct Point {
        int x, y;
        void read() {
            scanf("%d%d", &x, &y);
        }
    };
    
    Point a[1010];
    
    int main() {
        int n, photo = 1;
        while (scanf("%d", &n) == 1 && n) {
            for (int i = 0; i < n; i++) {
                a[i].read();
            }
            int best = 0;
            static double slopes[1010];
            for (int i = 0; i < n; i++) {
                int cnt = 0;
                for (int j = i + 1; j < n; j++) {
                    if (a[i].x == a[j].x) {
                        slopes[cnt++] = INF;
                    } else {
                        slopes[cnt++] = double(a[j].y - a[i].y) / (a[j].x - a[i].x);
                    }
                }
                sort(slopes, slopes + cnt);
                int local_max = 1;
                for (int j = 0; j < cnt; j++) {
                    int t = 1;
                    while (j + 1 < cnt && fabs(slopes[j] - slopes[j + 1]) < EPS) {
                        t++; j++;
                    }
                    local_max = max(local_max, t);
                }
                best = max(best, local_max + 1);
            }
            int eliminated = (best >= 4 ? best : 0);
            printf("Photo %d: %d points eliminated\n", photo++, eliminated);
        }
        return 0;
    }
    
    
    • 1

    信息

    ID
    1737
    时间
    2000ms
    内存
    64MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者