SP1709 SWTHIN - Swamp Things
题目描述
Hugh F. Oh 一直在努力证明外星生物的存在。他得到了一些研究小组拍摄的夜间照片,这些照片记录了发光的沼气。Hugh 想判断这些照片中是否藏着穿着发光服装的小灰人,而非单纯的沼气。在这些照片中,亮点在黑色背景上分布着。然而,拍摄时正有火车经过这一地区,其车窗的灯光偶尔也出现在照片中。作为一个严格的研究者,Hugh 希望能够把这些亮点从照片中剔除。
虽然无法确切知晓轨道的位置和拍摄的方向,Hugh 知道该区域的轨道是笔直的。因此,他决定采用以下方法:找出包含最多亮点的直线,如果这条直线上的点数达到四个或更多,就假定这些点来自火车窗,再从计算中剔除。如果有多条直线有相同数量最多的点,Hugh 将会随机选择一条直线进行剔除(他虽然执着,但也并不是一丝不苟的科学家——因为他相信小灰人的存在)。如果找不到任何一条直线上有不少于四个点,Hugh 将认为照片中没有火车亮点出现,无需剔除任何点。请为他编写一个程序来处理这些照片。
输入格式
输入包括若干组测试数据。每组数据代表一张照片:首先是一行正整数 $n$($n \leq 1000$),表示照片中亮点的数量。接下来是 $n$ 行,每行包含两个整数 $(x, y)$,表示每个亮点的坐标。所有坐标值都位于 $0$ 到 $10000$ 之间。输入的最后一行是一个零,表示输入结束,这一行不需要处理。
输出格式
对每组测试数据,输出照片编号和从照片中删除的亮点数量。请参考下方的输出示例。
**本翻译由 AI 自动生成**