2023河南萌新聯賽第（四）場：河南大學 F - 小富的idea

時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 262144K，其他語言524288K
64bit IO Format: %lld

題目描述

要注意節約

卷王小富最近又在內卷，并且學了一門新的技能：書法，但是不幸的是在國慶節的書法大賽上，小富不小心打翻了墨水瓶，導致很多墨滴濺在了他的書法紙上，看著墨水不斷擴散，浸透了他的書法紙，小富突然萌生了一個想法：我能不能知道某時刻紙上一共有多少墨塊？

我們假設墨滴是同時濺在紙上的，并且它們起始大小都為 $0$，由于墨滴大小不同，因此它們的擴散速度也不同，姑且假設墨滴都是按圓形擴散，如果兩個或以上墨滴在擴散過程中相遇，那么就稱它們為一個墨塊（單獨一個墨滴也是墨塊），并且假設墨滴相遇不影響它的擴散，對于任意時刻 $t$，小富想知道紙上有多少墨塊

由于小富是 $ccpc$ 金牌，這個問題對他來說簡直是小菜一碟，并且小富還要繼續他的書法大賽，于是他決定把這個問題交給你來解決，希望你不要辜負他的期望哦

輸入描述:

第一行一個整數 $n$，表示一共 $n$ 個墨滴 $(1\le n\le 10^3)$
接下來 $n$ 行，每行三個整數 $x,y,v$，分別表示墨滴的位置 $(x,y)$，以及墨滴擴散的速度 $v(0\le x,y,v\le 10^3)$
接下來一行一個整數 $q$，表示 $q$ 次查詢 $(0\le q,t\le 10^3)$
之后是 $q$ 行，每行一個整數 $t$ ，表示查詢 $t$ 時刻紙上一共多少個墨塊

輸出描述:

$q$ 行，每行一個整數，表示 ttt 時刻紙上一共多少個墨塊

輸入

3
0 2 1
0 0 1
7 7 2
3
0
1
5

輸出

3
2
1

說明

0時刻墨滴面積均為0，故答案為3
1時刻墨滴1，2相切，也記為相遇，故答案為2
5時刻三個墨滴都相遇，答案為1

對于任意一個墨滴，計算出它與其他所有墨滴的融合時間，并按時間從小到大排序，用并查集存儲所有墨滴，然后從小到大枚舉所有的融合時間，如果某個時間點發生兩個墨滴融合，那么當前時間之后紙上墨滴數就減一，當然，如果融合的墨滴本身就在一個墨塊里，總墨滴數不變標記出所有的墨滴減少的時間點，最后對于每次查詢，輸出當前墨滴數量即可

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;class edg implements Comparable<edg> {double d;int x, y;public edg(double d, int x, int y) {this.d = d;this.x = x;this.y = y;}@Overridepublic int compareTo(edg o) {return Double.compare(this.d, o.d);}
}public class Main {static int[] p = new int[1001];public static int find(int x) {if (x != p[x]) p[x] = find(p[x]);return p[x];}public static void main(String[] args) throws IOException {BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));int n = Integer.parseInt(bf.readLine());int[][] a = new int[n][3];for (int i = 0; i < n; i++) {String[] str = bf.readLine().split(" ");a[i][0] = Integer.parseInt(str[0]);a[i][1] = Integer.parseInt(str[1]);a[i][2] = Integer.parseInt(str[2]);p[i] = i;}ArrayList<edg> edgs = new ArrayList<>();for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {if (a[i][2] == 0 && a[j][2] == 0) continue;double D = Math.sqrt((a[i][0] - a[j][0]) * (a[i][0] - a[j][0]) + (a[i][1] - a[j][1]) * (a[i][1] - a[j][1]));double V = a[i][2] + a[j][2];edgs.add(new edg(D / V, i, j));}}Collections.sort(edgs);int[] res = new int[1001];int cnt = n;for (int i = 0, j = 0; i <= 1000; i++) {while (j < edgs.size() && edgs.get(j).d <= i) {int u = find(edgs.get(j).x), v = find(edgs.get(j).y);j++;if (u == v) continue;p[u] = v;cnt--;}res[i] = cnt;}int q = Integer.parseInt(bf.readLine());while (q-- > 0) {int t = Integer.parseInt(bf.readLine());bw.write(res[t] + "\n");}bw.close();}
}