Snapchat- 小车通过雷达区

题目描述: 有一条路,路两边可以想象为 y = 0 和y = 1两条直线。现在给你list of radar,每个雷达为(横坐标,纵坐标,辐射半径)。问你一辆车能否通过这条路。

分析& 代码

static class Radar {
    double x;
    double y;
    double r;
    public Radar(double x, double y, double r) {
        this.x = x;
        this.y = y;
        this.r = r;
    }
}

class Area {
    List<Radar> radars;
    double upperbound;
    double lowerbound;

    public Area() {
        radars = new ArrayList<Radar>();
        upperbound = 0;
        lowerbound = 1;
    }

    private boolean canMerge(Radar r1, Radar r2) {
        return Math.pow(r1.r + r2.r, 2) >= Math.pow(r1.x - r2.x, 2) + Math.pow(r1.y - r2.y, 2);
    }

    private boolean merge(Radar r) {
        for(Radar radar: radars) {
            if(canMerge(r, radar)) {
                upperbound = Math.max(upperbound, r.x + r.r);
                lowerbound = Math.min(lowerbound, r.y - r.r);
                radars.add(r);
                return true;
            }
        }
        return false;
    }

    private boolean cannotPass() {
        return upperbound >= 1 && lowerbound <= 0;
    }
}


public boolean canCarPass(List<Radar> radars) {
    List<Area> area = new ArrayList<Area>();
    for(Radar radar: radars) {
        boolean merged = false;
        for(Area a: area) {
            merged = a.merge(radar);
            if(merged) {
                break;
            }
        }
        if(!merged) {
            Area a = new Area();
            a.radars.add(radar);
            area.add(a);
        }
    }
    for(Area a : area) {
        if(a.cannotPass()) {
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    RadarDetect rd = new RadarDetect();
    //List<Radar> radars = Arrays.asList(new Radar(1, 0.5, 0.49), new Radar(3, 1.5, 1), new Radar(3, 0.4, 0.3));
    List<Radar> radars = Arrays.asList(new Radar(1, 0, 1.5), new Radar(3, 1, 1.5));
    System.out.println(rd.canCarPass(radars));
}

results matching ""

    No results matching ""