1 条题解
-
0
题意分析
给定 $n$ 个平面点,找出一条包含最多共线点的直线。如果该直线上的点数 $\ge 4$,则认为这些点属于火车车窗,应删除它们,反之不删除任何点。输出被删除的点数。
解题思路
-
对于每个点 $i$,将它与其它点 $j$ 的连线斜率 $k$ 记录下来,斜率定义为
$$ k = \begin{cases} \infty, & x_j = x_i;\\ \displaystyle\frac{y_j - y_i}{x_j - x_i}, & \text{其他}. \end{cases} $$ -
对每个 $i$,对该点到其他点的所有 $k$ 值排序,统计相同斜率的连续段长度,记最大值为 $m_i$。该点参与的最大共线点数为 $m_i + 1$(包括其自身)。
-
枚举所有 $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
- 上传者