lintcode 820 · 矩形【中等 vip 枚举法 数学】

题目

https://www.lintcode.com/problem/820/

给出一个 set，问能不能找到四个点组成平行于坐标轴的矩形，如果能输出 "YES"，否则输出 "NO"。


set 的点数小于 2000，坐标范围在 [-10000000,10000000]。
样例
样例 1：

输入：[[0,0],[0,1],[1,1],[1,0]]
输出："YES"
解释：set 中的四个点能组成平行于坐标轴的矩形。
样例 2：

输入：[[0,0],[0,1],[1,1],[2,0]]
输出："NO"
解释：set 中的四个点不能组成平行于坐标轴的矩形。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

思路

	转化为找平行线问题
    2个垂直的平行线，
    长度相同，初始点的y相同，x不同
1
2
3

答案

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */

public class Solution {
    /**
     * @param pointSet: The point set
     * @return: The answer
     */
    public String rectangle(Point[] pointSet) {
              /*
        转化为找平行线问题
        2个垂直的平行线，
        长度相同，初始点的y相同，x不同
         */
        List<Info> list = new ArrayList<>();
        for (int i = 0; i <pointSet.length ; i++) {
            for (int j = 0; j <pointSet.length; j++) {
                Point a = pointSet[i];
                Point b = pointSet[j];
                if(b.y > a.y && a.x ==b.x){
                    list.add(new Info(a,b,b.y-a.y));
                }
            }
        }

        for (int i = 0; i <list.size() ; i++) {
            for (int j = 0; j <list.size() ; j++) {
                Info a = list.get(i);
                Info b = list.get(j);

                if(a.len ==b.len && a.p1.x !=b.p1.x && a.p1.y ==b.p1.y){
                    return "YES";
                }
            }
        }

        return "NO";
    }

    static class Info{
        Point p1;
        Point p2;
        int len;
        public Info(Point a,Point b,int l){
            p1 = a;
            p2 =b;
            len =l;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57