Acwing.4737 冰壶

本文主要是介绍Acwing.4737 冰壶，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

红队和黄队进行了一场冰壶比赛，比赛结束后，裁判正在计算两队的得分。

场地可以看作一个二维平面，得分区域可以看作一个以 (0,0) 为圆心 Rh 为半径的圆。

场地上散落着 N 个红队的冰壶以及 M 个黄队的冰壶。

冰壶可以看作一个半径为 Rs 的圆。

每个冰壶的圆心坐标已知。

如果一个冰壶的任何部分位于得分区域的圆上或圆内（两者相切也算），则视为该冰壶位于得分区域内。

如果一个冰壶能够同时满足：

它位于得分区域内。
不存在任何对方冰壶比它距离得分中心 (0,0) 更近（欧几里得距离）。
那么，这个冰壶就是一个得分冰壶。

一个队伍的最终得分等于该队伍的得分冰壶数量。

请你计算并输出两支队伍的最终得分。

一个冰壶与得分中心之间的距离等于其圆心点到点 (0,0) 的距离。

数据保证不同冰壶与得分中心之间的距离不同，且冰壶两两之间不重叠（但可能相切）。

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含两个整数 Rs,Rh。

接下来一行包含一个整数 N。

接下来 N 行，每行包含两个整数 Xi,Yi，表示一个红队冰壶的圆心坐标为 (Xi,Yi)。

接下来一行包含一个整数 M。

接下来 M 行，每行包含两个整数 Zi,Wi，表示一个黄队冰壶的圆心坐标为 (Zi,Wi)。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为 Case #x: y z，其中 x 为组别编号（从 1 开始），y 为红队得分，z 为黄队得分。

数据范围

1≤T≤100,
1≤Rs<Rh≤104,
0≤N,M≤8,
−20000≤Xi,Yi,Zi,Wi≤20000

• 输入样例1：

2
1 5
4
1 -1
6 1
0 6
-5 0
0
10 100
2
-3 -4
200 200
0

• 输出样例1：

Case #1: 3 0
Case #2: 1 0

• 样例1解释
  Case 1 的冰壶分布情况如下图所示。

在这种情况下，黄队没有冰壶在得分区域内，所以红队在得分区域内的每个冰壶都是得分冰壶。

红队除了以 (6,1) 为圆心的那个冰壶以外，其他所有的冰壶都在得分区域内，所以红队得 3 分。

• 输入样例2：

2
1 5
2
1 0
-3 0
1
0 2
10 50
2
-40 -31
-35 70
3
59 0
-10 0
30 40

• 输出样例2：

Case #1: 1 0
Case #2: 0 2

• 样例2解释
  Case 1 的冰壶分布情况如下图所示。

在这种情况下，两支队伍都有冰壶在得分区域内。

红队圆心为 (1,0) 的冰壶在得分区域内，且没有黄队的冰壶比它距离得分中心更近，所以它值 1 分。

红队圆心为 (−3,0) 的冰壶在得分区域内，但是黄队圆心为 (0,2) 的冰壶比它距离得分中心更近，所以它不能得分。

黄队圆心为 (0,2) 的冰壶在得分区域内，但是红队圆心为 (1,0) 的冰壶比它距离得分中心更近，所以它不能得分。

因此，红队得 1 分，黄队得 0 分。

题解

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;/*** @author akuya* @create 2023-10-15-15:13*/
public class Main {static int t,tt,ttt;static double rs,rt;public static void main(String[] args) {Scanner scanner=new Scanner(System.in);t=scanner.nextInt();tt=t;while(t--!=0){int flag=3;rs=scanner.nextDouble();rt=scanner.nextDouble();Comparator<Entity> valueComparator = Comparator.comparing(Entity::getValue);// 创建优先队列并传入比较器PriorityQueue<Entity> priorityQueue = new PriorityQueue<>(valueComparator);int n=scanner.nextInt();while(n--!=0){int x=scanner.nextInt();int y=scanner.nextInt();double dis=Math.sqrt(x*x+y*y);if(dis<=rs+rt){priorityQueue.add(new Entity(dis,1));}}int m=scanner.nextInt();while(m--!=0){int x=scanner.nextInt();int y=scanner.nextInt();double dis=Math.sqrt(x*x+y*y);if(dis<=rs+rt){priorityQueue.add(new Entity(dis,2));}}int ans=0;while(!priorityQueue.isEmpty()){Entity en=priorityQueue.poll();if(flag==3||en.type==flag){ans++;flag=en.type;}else{break;}}ttt=tt-t;int l,r;if(flag==1){l=ans;r=0;}else{r=ans;l=0;}System.out.println("Case #"+ttt+": "+l+" "+r);}}public static class Entity {private double value;private int type;public Entity(double value, int type) {this.value = value;this.type = type;}public double getValue() {return value;}public int getType() {return type;}}}

思路

本题是一个简单的模拟枚举题，按照题目模拟，然后通过优先队列排序
最后进行判断即可。

这篇关于Acwing.4737 冰壶的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---