T1 逃离遗迹
根据外星人的回信,在遗迹中有分布着三样道具。当三样道具都拿走后,遗迹就很快自动毁灭,所以必须要在最短时间内离开。遗迹可以看作是由N个房间(编号1..N)和N-1条长度不等通道所组成,并且任意两个房间之间有且只有一条路可以相互到达。现在我们的队员已经在编号为A,B,C的房间内拿到道具,并且准备撤退。由于只有一架直升机,所以只能在一个房间上停留。现在请你决定将直升机停在哪一个房间之上,能够使三人到达该房间的距离之和最短。
考虑最短路模型,对 $A, ~ B, ~ C$ 三个点分别作为源点跑一次最短路,扫一遍所有的点,找到 $dist[A] + dist[B] + dist[C]$ 最小的点即可。
T2 遗址
标签:圆柱,dist,房间,道具,正方形,NZOJ,遗迹,模拟 From: https://www.cnblogs.com/YipChipqwq/p/18450848很久很久以前有一座寺庙,从上往下看寺庙的形状正好是一个正方形,在4个角上竖立着圆柱搭建而成。现在圆柱都倒塌了,只在地上留下圆形的痕迹,可是现在地上有很多这样的痕迹,专家说一定是最大的那个。
写一个程序,给出圆柱的坐标,找出由4个圆柱构成的最大的正方形,因为这就是寺庙的位置,要求计算出最大的面积。注意正方形的边不一定平行于坐标轴。
例如下图有10根柱子,其中(4,2),(5,2),(5,3),(4,3)可以形成一个正方形,(1,1),(4,0),(5,3),(2,4)也可以,后者是其中最大的,面积为10。
$![test]http://182.43.200.0:6548/upload/182.43.200.0:6548/image/20240911/20240911222325_14494.jpg$