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 矩阵判断 最详细的解题报告

hihoCoder 1040 矩阵判断最详细的解题报告