# 0963. Minimum Area Rectangle II
###### tags: `Leetcode` `Medium` `FaceBook`
Link: https://leetcode.com/problems/minimum-area-rectangle-ii/
## 思路
由于如果两条边长度相等且中点重合，那么两条边的四个顶点就可以构成一个矩形
所以用```Map<Double, Map<Point,List<Point>>>```,第一个key是边的长度，第二个key是center
用边长而不是center做第一个key是因为第31行，需要用center算另外一个点，然后求面积
对于两个点，先算出边长，然后算center，然后存进map里面，但只要存一个点就好了
后面对于每个边长每个center，把它存的点都拿出来，对于每两个点P和Q，先通过Q和center算出对于center对称的点Q2，已知三个点求矩形面积

在写这个题目的时候出现了一个bug，一开始我是自己建了一个class叫做point里面存x和y，但是由于没有**重写compare 或者 equals function**，存进map时候比对的是对象地址，所以对于每一个center，里面只有一个点，就会出bug
解决办法是用pair或者java.awt.Point

建议用java.awt.Point, 需要掌握的函数有
- get x和y值 直接a.x a.y
- new 对象 new Point(x,y)
## Code
用point

import java.awt.Point;
class Solution {
    public double computeLen(Point a, Point b){
        return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    }
    public double minAreaFreeRect(int[][] points) {
        Map<Double,Map<Point,List<Point>>> lenToPoints = new HashMap<>();
        Point[] pointSet = new Point[points.length];
        for(int i = 0;i < points.length;i++){
           pointSet[i] = new Point(points[i][0],points[i][1]); 
        }
        
        for(int i = 0;i < points.length-1;i++){
            for(int j = i+1;j < points.length;j++){
                //get center
                Point center = new Point(pointSet[i].x+pointSet[j].x, pointSet[i].y+pointSet[j].y);
                //get length
                double len = computeLen(pointSet[i],pointSet[j]);
                if(!lenToPoints.containsKey(len)){
                    lenToPoints.put(len, new HashMap<Point,List<Point>>());
                }
                
                Map<Point, List<Point>> centerToPoints = lenToPoints.get(len);
                
                if(!centerToPoints.containsKey(center)) centerToPoints.put(center, new ArrayList<>());
                centerToPoints.get(center).add(pointSet[i]);
            }
        }
        
        double minArea = Double.MAX_VALUE;
        for(Map<Point,List<Point>> info:lenToPoints.values()){
            for(Point center:info.keySet()){
                List<Point> candidates = info.get(center);
                for(int i = 0;i < candidates.size()-1;i++){
                    for(int j = i+1;j < candidates.size();j++){
                        Point P = candidates.get(i);
                        Point Q = candidates.get(j);
                        Point Q2 = new Point(center.x-Q.x, center.y-Q.y);
                        double area = Math.sqrt(computeLen(P,Q))*Math.sqrt(computeLen(P,Q2));
                        minArea = Math.min(minArea, area);                                         
                    }
                }
            }
        }
        return minArea==Double.MAX_VALUE?0:minArea;
    }
}

用pair 好复杂...

class Solution {
    public double minAreaFreeRect(int[][] points) {
        Map<Integer, Map<Pair<Integer, Integer>, List<Pair<Integer, Integer>>>> map = new HashMap<>();
        for(int i = 0;i < points.length-1;i++){
            for(int j = i+1;j < points.length;j++){
                Pair<Integer,Integer> a = new Pair<>(points[i][0], points[i][1]);
                Pair<Integer,Integer> b = new Pair<>(points[j][0], points[j][1]);
                int len = computeLen(a,b);
                Pair<Integer, Integer> center = getCenter(a,b);
                if(!map.containsKey(len)) map.put(len, new HashMap<>());
                Map<Pair<Integer, Integer>, List<Pair<Integer,Integer>>> subMap = map.get(len);
                if(!subMap.containsKey(center)) subMap.put(center, new ArrayList<>());
                subMap.get(center).add(a);
            }
        }
        
        double minArea = Double.MAX_VALUE;
        for(Map<Pair<Integer, Integer>, List<Pair<Integer, Integer>>> info:map.values()){
            for(Pair<Integer, Integer> center:info.keySet()){
                List<Pair<Integer, Integer>> candidates = info.get(center);
                for(int i = 0;i < candidates.size()-1;i++){
                    for(int j = i+1;j < candidates.size();j++){
                        Pair<Integer,Integer> a = candidates.get(i);
                        Pair<Integer,Integer> b = candidates.get(j);
                        Pair<Integer,Integer> c = getAnotherPoint(center, a);
                        double area = Math.sqrt(computeLen(a,b))*Math.sqrt(computeLen(b,c));
                        if(area < minArea){
                            minArea = area;
                        }
                        
                    }
                }
            } 
        }
        return minArea == Double.MAX_VALUE?0:minArea;
    }
    private int computeLen(Pair<Integer,Integer> a, Pair<Integer,Integer> b){
        return (a.getKey()-b.getKey())*(a.getKey()-b.getKey())+(a.getValue()-b.getValue())*(a.getValue()-b.getValue());
    }
    private Pair<Integer, Integer> getCenter(Pair<Integer,Integer> a, Pair<Integer,Integer> b){
        return new Pair<>(a.getKey()+b.getKey(),a.getValue()+b.getValue());
    }
    private Pair<Integer, Integer> getAnotherPoint(Pair<Integer,Integer> center, Pair<Integer, Integer> a){
        return new Pair<>(center.getKey()-a.getKey(),center.getValue()-a.getValue());
    }
}