java
-基于TreeMap
暴力做法
呜呜,暴力yyds,才不是没想到y总的做法尼(嘴硬中)
思路:bfs
枚举所有的导弹,如果炸弹能被引导,成为新的导弹,加入队列中
TreeMap
:这里用了自定义键值,记得key
对应的类完成比较函数就能用
key
:记录坐标但是会出现重叠比较难处理,这里的
value
也需要用个Pair
value
:记录半径和点数
//BFS暴力搜:相当极限不一定能过,差不多需要算1.6e8:1e5*100*Math.log(1e5)/Math.log(2)
//这里只能少量优化了
import java.util.*;
import java.io.*;
//这里需要用Pair作为键值去查
class Pair implements Comparable<Pair>{
@Override
public String toString() {
return "Pair [x=" + x + ", y=" + y + "]";
}
int x,y;
public Pair(int a,int b) {
x=a;
y=b;
}
Pair(){}
public int compareTo(Pair o) {//只用(x,y)来排
if(x==o.x)
return y-o.y;
return x-o.x;//服了我自己了,这里写叉了
}
}
class Node{
@Override
public String toString() {
return "Node [x=" + x + ", y=" + y + ", r=" + r + "]";
}
int x,y,r;
public Node(int x, int y, int r) {
super();
this.x = x;
this.y = y;
this.r = r;
}
}
public class Main{
static int n,m;
static Map<Pair,Pair> bomb=new TreeMap<>();//存下地图上所有炸弹
//key:记录坐标(x,y);value:前面记录半径和有多个雷
//这里r实际是不看的
static Queue<Node> q=new LinkedList<>();//存下所有的排雷火箭
public static void main(String[] args) throws Exception{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] ss=br.readLine().split(" ");
n=Integer.parseInt(ss[0]);
m=Integer.parseInt(ss[1]);
int[] p=new int[3];//存下那三个信息
for(int i=0;i<n;++i) {
ss=br.readLine().split(" ");
for(int j=0;j<3;++j)
p[j]=Integer.parseInt(ss[j]);
//会重复,只要记录最大的那个就行,但是这时还需要记录有几个
Pair t=new Pair(p[0],p[1]);
if(bomb.containsKey(t)) {
//记住value本质就是一个引用
//也就是说改变能直接作用再bomb中
Pair value=bomb.get(t);
value.x=Math.max(value.x,p[2]);
++value.y;
//这时候也不用更新了
}
else
bomb.put(t,new Pair(p[2],1));
}
// System.out.println(bomb);
for(int i=0;i<m;++i){
ss=br.readLine().split(" ");
for(int j=0;j<3;++j)
p[j]=Integer.parseInt(ss[j]);
q.add(new Node(p[0],p[1],p[2]));
}
//开始扫雷
int res=0;
while(!q.isEmpty()&&!bomb.isEmpty()) {
Node t=q.remove();
// System.out.println(t);
//遍历圆中的所有点
Pair tmp=new Pair();
for(int i=t.x-t.r;i<=t.x+t.r;++i) {
//确定列的左右界
int k=(int)Math.sqrt(t.r*t.r-(t.x-i)*(t.x-i));
for(int j=t.y-k;j<=t.y+k;++j) {
// System.out.println(i+" "+j);
tmp.x=i;tmp.y=j;
if(bomb.containsKey(tmp)) {
Pair value=bomb.get(tmp);
q.add(new Node(i,j,value.x));
res+=value.y;//这个位置藏了这么多炸弹
bomb.remove(tmp);//从炸弹中删去
}
}
}
}
System.out.println(res);
}
}