蓝桥杯（直线）Java

目录

• • 一、问题描述
  • 二、思路
  • 三、代码(java)

一、问题描述

二、思路

1. 第一点：用一个hash存储遍历所得的每条直线，最后求出hash长度，这一点都很容易想到，但hash的存储形式确是一个关键
2. 要比较两个直线是否为同一条直线，考虑到点斜式的斜率计算时为浮点数，不够精确，所以这里采用直线的标准形式，即Ax+By+C=0的三个系数A、B、C必须同比列相等，所以我们可以求出他们三个的最大公约数，将直线化到最简进行存储
3. 由直线的两点式方程(y-y1)/(y2-y1)=(x-x1)/(x2-x1),化简得到 A=y1-y2,B=x2-x1,C=x1*(y2-y1)-y1*(x2-x1)
4. 三个数的最大公约求解：先算出最小的两个数的最大公约数g，再求出g与最大数的最大公约数，即为三个数的最大公约数
5. 最开始想的是用一个由A、B、C组成的结点放入hash，但得重写hashcode，equals方法，比较麻烦，最后想到可以用字符串形式进行存储
6. 我这里只计算了斜线，最后加上斜率为0和斜率为1的20+21条直线即为最终答案

三、代码(java)

import java.util.Arrays;import java.util.HashSet;public class Main {public static void main(String[] args) {// TODO Auto-generated method stubint sum = 21 + 20;HashSet<String> set =  new HashSet<String>();for(int x1 = 0;x1 < 20;x1++) {for(int y1 = 0;y1 < 21;y1++) {for(int x2 = x1+1;x2 < 20;x2++) {for(int y2 = 0;y2 < 21;y2++) {if(x1 != x2 && y1 != y2) {int[] abc = {y1-y2,x2-x1,x1*(y2-y1)-y1*(x2-x1)};Arrays.sort(abc);int g = gcd(abc[1], abc[0]);int gc = gcd(abc[2], g);int A = (y1-y2)/gc;int B = (x2-x1)/gc;int C = (x1*(y2-y1)-y1*(x2-x1))/gc;set.add(A+" "+B+" "+C);}}}}}System.out.println(set.size()+sum);}static int gcd(int x, int y) {return x%y == 0 ? y : gcd(y, x%y);}}

答案：40257

素彩网