首页 > 代码库 > hihoCoder 1040 矩阵判断
hihoCoder 1040 矩阵判断
题目来源：矩阵判断
解题思路：
1、判断矩阵的4个点是否相连，一共输入8个点，只要判断是否4个点是否都经过2遍；
2、判断矩阵中任意一条边与其他边之间要么平行，要么垂直。设A（x1，y1），B（x2，y2），C（x3，y3），D（x4，y4），则线段AB的向量为A’（x2-x1，y2-y1），线段CD的向量C‘（x4-x3，y4-y3），另x2-x1=a1，y2-y1=a2，x4-x3=c1，y4-y3=c2，判断A’是否平行C‘的方法是a1*c2-a2*c1=0；判断A’是否垂直C‘的方法是a1*c1+a2*c2=0.
具体算法（java版，可以直接AC）
1 import java.util.ArrayList; 2 import java.util.List; 3 import java.util.Scanner; 4 5 public class Main { 6 7 public static boolean isCycled(List<Line> list) { 8 List<Point> temp = new ArrayList<Point>(); 9 for (Line line : list) { 10 if (line.getDistance() == 0)// 保证面积大于0 11 return false; 12 if (temp.contains(line.start)) { 13 temp.remove(line.start); 14 } else { 15 temp.add(line.start); 16 } 17 if (temp.contains(line.end)) { 18 temp.remove(line.end); 19 } else { 20 temp.add(line.end); 21 } 22 } 23 return temp.size() == 0; 24 } 25 26 public static void main(String[] args) { 27 Scanner scanner = new Scanner(System.in); 28 int n = scanner.nextInt(); 29 List<Line> list = new ArrayList<Line>(); 30 for (int i = 0; i < n; i++) { 31 list.clear(); 32 for (int j = 0; j < 4; j++) { 33 list.add(new Line(scanner.nextInt(), scanner.nextInt(), scanner 34 .nextInt(), scanner.nextInt())); 35 } 36 boolean ans = true; 37 if (isCycled(list)) { 38 for (int j = 0; j < 4; j++) { 39 for (int k = j + 1; k < 4; k++) { 40 if (!list.get(j).isVerticalOrParallel(list.get(k))) { 41 ans = false; 42 break; 43 } 44 } 45 if (!ans) 46 break; 47 } 48 } else { 49 ans = false; 50 } 51 if (ans) { 52 System.out.println("YES"); 53 } else { 54 System.out.println("NO"); 55 } 56 } 57 } 58 59 } 60 61 class Point { 62 public int x; 63 public int y; 64 65 public Point(int x, int y) { 66 this.x = x; 67 this.y = y; 68 } 69 70 public boolean equals(Object o) { 71 if (this == o) 72 return true; 73 if (o instanceof Point) { 74 Point p = (Point) o; 75 return this.x == p.x && this.y == p.y; 76 } 77 return false; 78 } 79 80 public int hashCode() { 81 return this.x * 10 + this.y; 82 } 83 } 84 85 class Line { 86 public Point start; 87 public Point end; 88 89 public Line(int x1, int y1, int x2, int y2) { 90 this.start = new Point(x1, y1); 91 this.end = new Point(x2, y2); 92 } 93 94 private Point getVector() { 95 return new Point(this.end.x - this.start.x, this.end.y - this.start.y); 96 } 97 98 private boolean isVertical(Line line) { 99 Point p1 = this.getVector();100 Point p2 = line.getVector();101 return p1.x * p2.x + p1.y * p2.y == 0;102 }103 104 private boolean isParallel(Line line) {105 Point p1 = this.getVector();106 Point p2 = line.getVector();107 return p1.x * p2.y - p1.y * p2.x == 0;108 }109 110 public int getDistance() {111 return (int) ((this.start.x - this.end.x) * (this.start.x - this.end.x) + (this.start.y - this.end.y)112 * (this.start.y - this.end.y));113 }114 115 public boolean isVerticalOrParallel(Line line) {116 return this.isParallel(line) || this.isVertical(line);117 }118 }
hihoCoder 1040 矩阵判断
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。