【蓝桥杯集训·每日一题】AcWing 4309. 消灭老鼠

写在前面

本人CSDN博客主页：这里

一、题目

1、原题链接

4309. 消灭老鼠

2、题目描述

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

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

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

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

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

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

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

输入格式

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

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

输出格式

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

数据范围

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

输入样例1：

4 0 0 1 1 2 2 2 0 -1 -1

输出样例1：

2

输入样例2：

2 1 2 1 1 1 0

输出样例2：

1

二、解题报告

1、思路分析

思路来源：y总讲解视频 y总yyds

（1）我们可以先将发射点移动到原点，当某些点与发射点构成的直线的斜率相同时，说明可以将这些点上的老鼠一起消灭掉。 （2）由于可能有些点在x轴或者y轴上，所以计算斜率可能会出现除数为0的情况，所以我们用点对来存储每个点的斜率（即分子分母约分后最简分数形式的点对（分子与分母），也就是同时除以它俩的最大公约数）。而针对一条直线，可以同时消灭一、三象限或二、四象限点上在该直线上的所有老鼠，所以我们可以将二、四象限的点来原点对称到第一、四象限（针对两个点，如果某个点经过原点对称变换后和另外一个点重合，说明两点在同一条直线上），所以，这样我们只需要统计第一、四象限有多少个点对即可。 （3）最后统计一共有多少个不同的点对即可。

2、时间复杂度

时间复杂度为O(nlogn)（求最大公约数时间复杂度O(logn)）

3、代码详解

#include <iostream>
#include <set>
#include <utility>
using namespace std;
typedef pair<int,int> PII;    //存储每个点对
set<PII> s;             //set去重来统计点对个数
int n,x0,y0;
//欧几里得算法求最大公约数
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
int main(){
    cin>>n>>x0>>y0;
    while(n--){
        int x,y;
        cin>>x>>y;
        x-=x0,y-=y0;       //将该点坐标更新成以(x0,y0)为原点的坐标系中点的坐标
        int d=gcd(x,y);    //求两者的最大公约数
        x/=d,y/=d;         //将y/x分子分母约分（分子分母同时除两者的最大公约数）后的点对放入set中
        if(x<0) x=-x,y=-y; //将第二、三象限的点原点对称到第一、四象限
        s.insert({x,y});
    }
    cout<<s.size();
    return 0;
}

三、知识风暴

最大公约数

• 求最大公约数可以利用欧几里得算法：即gcd(a,b)=gcd(b,a mod b)。