目录

求最大公约数模板

4309. 消灭老鼠 - 约分去重

求最大公约数模板

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

4309. 消灭老鼠 - 约分去重

4309. 消灭老鼠 - AcWing题库

题目：

有n个老鼠，坐标点(x0,y0)有一台灭鼠仪，可以将某一个斜率直线上的老鼠全部消灭

给出n个老鼠的坐标，问至少多少次射击可将全部老鼠消灭

思路：

• 一条斜率相同的直线上的点记作一次射击
• 因此只要枚举老鼠，计算斜率，相同即在一条直线上
• 但直接算存在精度问题，因此我们算出x-x0，y-y0，然后将分子分母约分
• 存入set中去重，在一条直线上的点约分后的值肯定相同
• 最后输出set.size 
• java set不能去重类PII

/**道阻且长，行则将至*author:Roye_ack
*/
import java.util.*;
import java.io.*;
import java.math.*;class Main
{static PrintWriter wt=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));static int N=150100;public static int gcd(int a,int b){return b!=0? gcd(b,a%b):a;}public static void main(String[] args) throws IOException{int n=rd.nextInt();int x0=rd.nextInt(),y0=rd.nextInt();Set st=new HashSet<>();while(n-->0){int x=rd.nextInt(),y=rd.nextInt();x-=x0; y-=y0;int t=gcd(x,y);x/=t; y/=t;if(x<0)  //将第二象限的映射到第四象限，将第三象限映射到第一象限{x=-x;y=-y;}String tt=x+" "+y;st.add(tt);}int res=st.size();wt.print(res);wt.flush();}static class rd{static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));static StringTokenizer tk=new StringTokenizer("");static String nextLine() throws IOException{return bf.readLine();}static String next() throws IOException{while(!tk.hasMoreTokens()) tk=new StringTokenizer(bf.readLine());return tk.nextToken();}static int nextInt() throws IOException{return Integer.parseInt(next());}static double nextDouble() throws IOException{return Double.parseDouble(next());}static long nextLong() throws IOException{return Long.parseLong(next());}static BigInteger nextBig() throws IOException{BigInteger d=new BigInteger(rd.nextLine());return d;}}
}class PII 
{public int x;public int y;public PII(int cx,int cy){cx=x;cy=y;}/*public int compareTo(PII o){return Integer.compare(x,o.x);}*/
}