2021年第12届蓝桥杯竞赛

第一题：《直线》

题目大意

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

在平面直角坐标系中，两点可以确定一条直线。

给定平面上 20 × 2120×21 个整点 {(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z}(x,y)∣0≤x<20,0≤y<21,x∈Z,y∈Z，即横坐标是 00 到

1919 (包含 00 和 1919) 之间的整数、纵坐标是 00 到 2020 (包含 00 和 2020) 之 间的整数的点。

请问这些点一共确定了多少条不同的直线。

解题思路

在平面直角坐标系中，俩点可以确定一条直线，那俩点有四个坐标值，我们不太好维护四个坐标值是否重复。

我们知道直线的表示方式中，除了俩点式，还有点斜式，点斜式的话， 一个点俩个坐标值和一个斜率值，三个值来确定唯一性，虽然不太好写但是还是勉强能跑出来。

选择y = kx + b 这条方程来代表直线。我们怎么表示K呢，我是定义一个string字符串，存储分子和分母，这样就不用担心小数的问题了。

如下面代码，先存储420个点到 list 集合中。

		int x = 19, y = 20;
		ArrayList<Integer> list = new ArrayList<Integer>();
		//存储420个点的坐标
		for (int i = 0; i <= x; i++) {
			for (int j = 0; j <= y; j++) {
				list.add(i*100 + j);
			}	

然后定义 HashSet 集合保存不重复的斜率和截距的直线（因为一个斜率和截距可以确定一条直线）

HashSet<String> set = new HashSet<String>();

然后嵌套两个 for 循环，遍历所有的点，（两层for循环代表第一个点和第二个点）

for (int i = 0; i < list.size(); i++) {
			for (int j = i+1; j < list.size(); j++) {

然后先找斜率：

                int a = list.get(i);
				int b = list.get(j);
				int x1 = a/100;
				int y1 = a%100;
				int x2 = b/100;
				int y2 = b%100;
				int down = x2 - x1;
				int up =   y2 - y1;
				//if (down!=0 && up !=0) {
					/**
					 * 求斜率
					 */
					int gcd = gcd(down, up);
					String s = (up / gcd) + "/" + (down / gcd);
///当分母为0使，代表斜率不存在，此时存储直线 (x = 0:代表过点（0，0），斜率不存在的直线)
					  if (down == 0) {
		                    set.add("x = " + x1);
		                    continue;
		                }

再求截距：

                     /**
					 * 求截距
					 */
					int y_down = y1 * down;
					int x_up   = x1 *up;
					int up2 = y_down - x_up;
					int gcd2 = gcd(up2, down);
					String s2 =(up2/gcd2) + "/" + (down/gcd2);

最后将截距和斜率字符串加入到 Set 集合；

set.add(s+" "+s2);

因为把分子分母分开存储，所以不要忘了约分，求分子和分母的最大公因数。

    public static int gcd(int m,int n){
		return n==0?m:gcd(n,m%n);
	}

完整代码：

import java.util.ArrayList;
import java.util.HashSet;
/*
 * 本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
         在平面直角坐标系中，两点可以确定一条直线。
          给定平面上 20 × 2120×21​ 个整点
   {(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z}(x,y)∣0≤x<20,0≤y<21,x∈Z,y∈Z​，
           即横坐标是 00​ 到 1919​ (包含 00​ 和 1919​) 之间的整数
	 纵坐标是 00​ 到 2020​ (包含 00​ 和 2020​​) 之 间的整数的点。
	请问这些点一共确定了多少条不同的直线。
*/
public class 直线_1_2021 {
	public static void main(String[] args) {
		int x = 19, y = 20;
		ArrayList<Integer> list = new ArrayList<Integer>();
		//存储420个点的坐标
		for (int i = 0; i <= x; i++) {
			for (int j = 0; j <= y; j++) {
				list.add(i*100 + j);
			}
		}		
		HashSet<String> set = new HashSet<String>();
		//System.out.println(list.size());
		for (int i = 0; i < list.size(); i++) {
			int a = list.get(i);
			for (int j = i+1; j < list.size(); j++) {
				int b = list.get(j);
				int x1 = a/100;
				int y1 = a%100;
				int x2 = b/100;
				int y2 = b%100;
				int down = x2 - x1;
				int up =   y2 - y1;
				//if (down!=0 && up !=0) {
					/**
					 * 求斜率
					 */
					int gcd = gcd(down, up);
					String s = (up / gcd) + "/" + (down / gcd);
					/**
					 * 求截距
					 */
					  if (down == 0) {
		                    set.add("x = " + x1);
		                    continue;
		                }
					int y_down = y1 * down;
					int x_up   = x1 *up;
					int up2 = y_down - x_up;
					int gcd2 = gcd(up2, down);
					String s2 =(up2/gcd2) + "/" + (down/gcd2);
					/*
					 * 斜率和截距加入set集合
					 */
					set.add(s+" "+s2);
				//}
			}
		}	
		System.out.println(set.size());
	}
	//求最大公因数
    public static int gcd(int m,int n){
		return n==0?m:gcd(n,m%n);
	}
		
}

最终答案：40257。