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。