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));
}