[蓝桥杯 2024 国 B] 蚂蚁开会

问题描述

二维平面上有 n 只蚂蚁，每只蚂蚁有一条线段作为活动范围，第 i 只蚂蚁的活动范围的两个端点为 (uix,uiy),(vix,viy)。现在蚂蚁们考虑在这些线段的交点处设置会议中心。为了尽可能节省经费，它们决定只在所有交点为整点的地方设置会议中心，请问需要设置多少个会议中心？

输入格式

输入共 n+1 行。第一行为一个正整数 n。后面 n 行，每行 4 个由空格分开的整数表示 uix,uiy,vix,viy​。

输出格式

输出共 1 行，一个整数表示答案。

样例输入

4
0 0 4 4
0 4 4 0
2 0 0 4
2 1 2 3

样例输出

2

样例说明

所有线段之间共有 3 个不同的交点：(0,4),(4,3),(2,2)，其中整点有 2 个：(0,4),(2,2)。

评测用例规模与约定

对于 20% 的评测用例，保证 0≤uix,uiy,vix,viy≤100。

对于 100% 的评测用例，保证 n≤500,0≤uix,uiy,vix,viy≤10000，保证任意蚂蚁的活动范围不会退化成一个点，不保证任意两条线段之间交点数量有限。

解题思路：

问需要设置多少个会议中心，即找出所有交点为整点的地方。

整点，顾名思义，横纵坐标为整数的点，样例(4,3)这个点挺迷惑的，直接按题目意思来即可。

要找出这些点，我们可以通过找到每条线段上的整点，再对这些整点出现的次数进行统计，次数>=2的即为交点，也就是设置会议中心的点。

要找到每条线段上的整点，涉及数学知识，为以下式子：

//p1,p2为两个端点，p1.x为一个端点的横坐标，p1.y为纵坐标
int dx=p2.x-p1.x;//dx和dy表示从p1到p2在x和y方向上的变化量
int dy=p2.y-p1.y;
int gcd=Math.abs(gcd(dx,dy));//gcd是两个数的最大公约数,决定了线段上整数点的分布密度
//例如：如果dx=3和dy=6，则gcd=3，说明线段上有3+1=4个整数点
//这些点的间隔为(dx/gcd, dy/gcd) = (1, 2)
int stepX=dx/gcd;//stepX和stepY表示从一个整数点到下一个整数点的坐标变化量
int stepY=dy/gcd;
int step=gcd;//代表有step个整数点

 代码：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;public class Main {static class Point{int x,y;public Point(int x,int y) {this.x=x;this.y=y;}// 重写hashCode和equals方法，确保HashMap能正确识别相同坐标的点//将自定义对象（如Point类）用作HashMap或HashSet的键时，必须重写hashCode()和equals()方法@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Point point = (Point) o;return x == point.x && y == point.y;}@Overridepublic int hashCode() {return java.util.Objects.hash(x, y);}}public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();Map<Point,Integer> pointCount=new HashMap<>();for(int i=0;i<n;i++) {int x1=sc.nextInt();int y1=sc.nextInt();int x2=sc.nextInt();int y2=sc.nextInt();Point p1=new Point(x1,y1);Point p2=new Point(x2,y2);List<Point> points=new ArrayList<>();points=getPoints(p1,p2);//计算两个端点p1,p2之间存在多少整点for(Point p:points) {pointCount.put(p,pointCount.getOrDefault(p, 0)+1);//对每个整点出现的次数进行计数}}//寻找出现次数>=2的整点，计数int count=0;for(Map.Entry<Point, Integer> entry:pointCount.entrySet()) {if(entry.getValue()>=2) {count++;}}System.out.println(count);}private static List<Point> getPoints(Point p1,Point p2){List<Point> points=new ArrayList<>();int dx=p2.x-p1.x;int dy=p2.y-p1.y;int gcd=Math.abs(gcd(dx,dy));int stepX=dx/gcd;int stepY=dy/gcd;int step=gcd;for(int i=0;i<=step;i++) {//遍历寻找所有整点int x=p1.x+i*stepX;int y=p1.y+i*stepY;points.add(new Point(x,y));//存储每个整点}return points;}private static int gcd(int a,int b) {return b==0?a:gcd(b,a%b);}}