网站建设容易吗,中企动力企业邮箱手机app,我花钱买了一个函授本科,西安晨曦e动网站建设2023河南萌新联赛第#xff08;四#xff09;场#xff1a;河南大学 F - 小富的idea 时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒 空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K 64bit IO Format: %lld 题目描述 要注意节约 卷王小富最近又在内卷四场河南大学 F - 小富的idea 时间限制C/C 1秒其他语言2秒 空间限制C/C 262144K其他语言524288K 64bit IO Format: %lld 题目描述 要注意节约 卷王小富最近又在内卷并且学了一门新的技能书法但是不幸的是在国庆节的书法大赛上小富不小心打翻了墨水瓶导致很多墨滴溅在了他的书法纸上看着墨水不断扩散浸透了他的书法纸小富突然萌生了一个想法我能不能知道某时刻纸上一共有多少墨块
我们假设墨滴是同时溅在纸上的并且它们起始大小都为 0 0 0由于墨滴大小不同因此它们的扩散速度也不同姑且假设墨滴都是按圆形扩散如果两个或以上墨滴在扩散过程中相遇那么就称它们为一个墨块单独一个墨滴也是墨块并且假设墨滴相遇不影响它的扩散对于任意时刻 t t t小富想知道纸上有多少墨块
由于小富是 c c p c ccpc ccpc 金牌这个问题对他来说简直是小菜一碟并且小富还要继续他的书法大赛于是他决定把这个问题交给你来解决希望你不要辜负他的期望哦
输入描述:
第一行一个整数 n n n表示一共 n n n 个墨滴 ( 1 ≤ n ≤ 1 0 3 ) (1\le n \le 10^3) (1≤n≤103) 接下来 n n n 行每行三个整数 x , y , v x,y,v x,y,v分别表示墨滴的位置 ( x , y ) (x,y) (x,y)以及墨滴扩散的速度 v ( 0 ≤ x , y , v ≤ 1 0 3 ) v(0\le x, y, v\le10^3) v(0≤x,y,v≤103) 接下来一行一个整数 q q q表示 q q q 次查询 ( 0 ≤ q , t ≤ 1 0 3 ) (0\le q,t \le 10^3) (0≤q,t≤103) 之后是 q q q 行每行一个整数 t t t 表示查询 t t t 时刻纸上一共多少个墨块
输出描述: q q q 行每行一个整数表示 ttt 时刻纸上一共多少个墨块
输入
3
0 2 1
0 0 1
7 7 2
3
0
1
5输出
3
2
1说明
0时刻墨滴面积均为0故答案为3
1时刻墨滴12相切也记为相遇故答案为2
5时刻三个墨滴都相遇答案为1对于任意一个墨滴计算出它与其他所有墨滴的融合时间并按时间从小到大排序用并查集存储所有墨滴然后从小到大枚举所有的融合时间如果某个时间点发生两个墨滴融合那么当前时间之后纸上墨滴数就减一当然如果融合的墨滴本身就在一个墨块里总墨滴数不变标记出所有的墨滴减少的时间点最后对于每次查询输出当前墨滴数量即可
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;class edg implements Comparableedg {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;}ArrayListedg 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();}
}
