题目信息

题目类型
练习
题目年份
2025
题目题型
编程题
关 键 词
扩散

题目题干

扩散

【题目描述】

一个点每过一个单位时间就会向四个方向扩散一个距离,如图。u81100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

扩散  【题目描述】 一个点每过一个单位时间就会向四个方向扩散一个距离,如图。    两个点a、b连通,记作e(a,b),当且仅当a、b的扩散区域有公共部分。连通块的定义是块内的任意两个点u、vu、v都必定存在路径e(u,a0),e(a0,a1),…,e(ak,v)。给定平面上的n给点,问最早什么时刻它们形成一个连通块。  【输入】 第一行一个数n,以下n行,每行一个点坐标。  【输出】 一个数,表示最早的时刻所有点形成连通块。  【输入样例】 2 0 0 5 5 【输出样例】 5 【提示】 【数据规模】  对于20%的数据,满足1≤N≤5;1≤X[i],Y[i]≤50;  对于100%的数据,满足1≤N≤50;1≤X[i],Y[i]≤10^9。u81100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

两个点a、b连通,记作e(a,b),当且仅当a、b的扩散区域有公共部分。连通块的定义是块内的任意两个点u、vu、v都必定存在路径e(u,a0),e(a0,a1),…,e(ak,v)。给定平面上的n给点,问最早什么时刻它们形成一个连通块。u81100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【输入】

第一行一个数n,以下n行,每行一个点坐标。u81100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【输出】

一个数,表示最早的时刻所有点形成连通块。u81100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

【输入样例】

2
0 0
5 5

【输出样例】

5

【提示】

【数据规模】u81100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

对于20%的数据,满足1≤N≤5;1≤X[i],Y[i]≤50;u81100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

对于100%的数据,满足1≤N≤50;1≤X[i],Y[i]≤10^9。u81100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

答案解析

相关题目

灯泡 【题目描述】 相比wildleopard的家,他的弟弟mildleopard比较穷。他的房子是狭窄的而且在他的房间里面仅有一个灯泡。每天晚上,他徘徊在自己狭小的房子里,思考如何赚更多的钱。有一
扩散 【题目描述】 一个点每过一个单位时间就会向四个方向扩散一个距离,如图。 两个点a、b连通,记作e(a,b),当且仅当a、b的扩散区域有公共部分。连通块的定义是块内的任意两个点u、vu、v
数列分段II 【题目描述】 对于给定的一个长度为N的正整数数列A[i],现要将其分成M(M≤N)段,并要求每段连续,且每段和的最大值最小。 关于最大值最小: 例如一数列4 2 4 5 1要分成3段
曲线 【题目描述】 明明做作业的时候遇到了n个二次函数Si(x)=ax²+bx+c,他突发奇想设计了一个新的函数F(x)=max(Si(x)), i=1,2...n。 明明现在想求这个函数在[0,1
Best Cow Fences 【题目描述】 给定一个长度为n的正整数序列A。求一个平均数最大的,长度不小于L的子序列。 【输入】 第一行,n和L; n个正整数,表示A。 【输出】 一个整数,
糖果传递 【题目描述】 有n个小朋友坐成一圈,每人有aiai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。 【输入】 第一行一个正整数n≤1000000,表示小朋友的个数. 接
钓鱼 【题目描述】 在一条水平路边,有 n个钓鱼湖,从左到右编号为 1,2,…,n。佳佳有 H个小时的空余时间,他希望利用这个时间钓到更多的鱼。他从 1 出发,向右走,有选择的在一些湖边停留一定的时间
家庭作业 【题目描述】 老师在开学第一天就把所有作业都布置了,每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为10,要求在6天内交,那么要想拿
线段 【题目描述】 在一个数轴上有n条线段,现选取其中kk条线段使得这kk条线段两两没有重合部分,问最大的kk为多少? 【输入】 第一行为一个正整数n,下面n行每行2个数字ai,bi,描述每条线段
数列分段 【题目描述】 对于给定的一个长度为N的正整数数列A[i],现要将其分成连续的若干段,并且每段和不超过M(可以等于M),问最少能将其分成多少段使得满足要求。 【输入】 第1行包含两个正整数

提示声明

  • 免责声明:本站资源均来自网络或者用户投稿,仅供用于学习和交流:如有侵权联系删除!
  • 温馨提示:本文属于积分文章,需要充值获得积分或升级VIP会员,也可在会员中心投稿获取。

猜你喜欢