4309. 消灭老鼠

一. 题目详情

约翰的农场可以看作一个二维平面。

农场中有 n 个老鼠，在毁坏着农田。

第 i个老鼠的位置坐标为 (xi,yi)。

不同老鼠可能位于同一位置。

在 (x0,y0)处，装有一个双向发射的激光枪，该位置没有老鼠。

激光枪每次发射都可以将穿过点 (x0,y0) 的某一条直线上的所有老鼠都消灭掉。

请问，为了消灭所有老鼠，至少需要激光枪发射几次。

输入格式

第一行包含三个整数 n,x0,y0表示共有 n 只老鼠，激光枪的位置为 (x0,y0)。

接下来 n 行，每行包含两个整数 xi,yi 表示第 ii 只老鼠的位置为 (xi,yi)。

输出格式

一个整数，表示激光枪的最少发射次数。

数据范围

前 55 个测试点满足 1≤n≤5。
所有测试点满足 1≤n≤1000，−104≤xi,yi≤104。

输入样例1：

1
2
3
4
5
4 0 0
1 1
2 2
2 0
-1 -1

输出样例1：

1
2

输入样例2：

1
2
3
2 1 2
1 1
1 0

输出样例2：

1
1

二. 问题梳理

因为激光枪射线是双向发射的，所以此题为经典的直线扫描在四周问题，我们的目光主要集中在如下几个方面

  1. 怎样表达直线，有斜率截距法、向量法等
  2. 怎样存储直线
  3. 怎样判断直线是否已经存在

三. 作者代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        //输入x0,y0
        int x0 = scanner.nextInt();
        int y0 = scanner.nextInt();
        HashSet set = new HashSet();
        int y,x,count = 0;

        for (int i = 0; i < n; i++) {
			//输入小鼠位置
            x = scanner.nextInt();
            y = scanner.nextInt();
            //求向量（x-x0，y-y0）
            x -= x0;y -= y0;
            //求x,y的最大公约数，求双方向量
            int mod =gcd(x,y);
            //除双方最大公约数
            x /=mod;y /=mod;
            //因为向量是有方向的，所以我们统一把x都设为正
            //这样一条直线的不同方向向量变成了一个方向
            if(x<0){x = -x;y = -y;}
            //数据范围内不重复存储
            int temp = x*10000+y;

            //储存进set中，若已经存在则不加入，count记录直线数目
            if(!set.contains(temp)){
                count++;
                set.add(temp);
            }
        }
        System.out.println(count);
    }

    public static int gcd(int a,int b){
        while (b!=0){
            int temp = a%b;
            a = b;
            b = temp;
        }
        return a;
    }
}