卖挂的网站怎么做,河北中冶润丰建设股份有限公司网站,合肥网站建设q479185700棒,中国建设学会查询网站文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴最大公约数一、题目
1、原题链接 4309. 消灭老鼠 2、题目描述 约翰的农场可以看作一个二维平面。 农场中有 n 个老鼠#xff0c;在毁坏着农田。 第 i 个老鼠的位置坐标为…
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴最大公约数一、题目
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−104≤xi,yi≤104。 输入样例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 pairint,int PII; //存储每个点对
setPII s; //set去重来统计点对个数
int n,x0,y0;
//欧几里得算法求最大公约数
int gcd(int a,int b){return b?gcd(b,a%b):a;
}
int main(){cinnx0y0;while(n--){int x,y;cinxy;x-x0,y-y0; //将该点坐标更新成以(x0,y0)为原点的坐标系中点的坐标int dgcd(x,y); //求两者的最大公约数x/d,y/d; //将y/x分子分母约分分子分母同时除两者的最大公约数后的点对放入set中if(x0) x-x,y-y; //将第二、三象限的点原点对称到第一、四象限s.insert({x,y});}couts.size();return 0;
}三、知识风暴 最大公约数 求最大公约数可以利用欧几里得算法即gcd(a,b)gcd(b,a mod b)。
