人工翻译
查看原帖
人工翻译
1029721
AnsonIsTheBest楼主2024/3/21 20:31

贝西正要从一趟长途旅行中回来,Farmer John想要在她的牧场里布置一个“欢迎回家”的横幅来迎接她。这个横幅将会拴在一个范围为L1到L2 (1 <= L1 <= L2; L1 <= L2 <= 1,500)的线的两端

牧场面积为W × H (1 <= W <= 1000;1 <= H <= 1000),并且Farmer John在每个整数坐标的点都安装了一个杆子。在这(W + 1) * (H + 1)点中,Farmer John必须选择两个点来固定他将悬挂旗帜的线的两端。

FJ希望他的旗帜挂上去之后不会被挡住,所以在两个柱子之间的线上不能有其他柱子。

Farmer John需要你的帮助来计算出他有多少种可能的方式来悬挂横幅。他知道这个数字很大,一个32位的整数可能不足以计算出答案。

示例,W = 2, H = 1: 横幅大小在2到3的范围内。这个牧场包含(2+1)(1+1)= 6个点,并且有(6选2)=(65)/(2*1)= 15个不同的潜在点对,在这些点之间可以拉出这几条线:


(0,0)-(0,1)   (0,0)-(2,1)   (0,1)-(2,1)   (1,1)-(2,0) 
(0,0)-(1,0)   (0,1)-(1,0)   (1,0)-(1,1)   (1,1)-(2,1) 
(0,0)-(1,1)   (0,1)-(1,1)   (1,0)-(2,0)   (2,0)-(2,1) 
(0,0)-(2,0)   (0,1)-(2,0)   (1,0)-(2,1)

在这些对中,只有四个的长度在2..3的范围内:

(0,0)-(2,0) 2.00

(0,1)-(2,0) 2.24

(0,0)-(2,1) 2.24

(0,1)-(2,1) 2.00

在这四个中,(0,0)-(2,0)和(0,1)-(2,1)在端点之间的直线上都有一个柱子,因此是不合适的。

所以,15对点中只有两对点可以作为悬挂横幅线的候选点。

2024/3/21 20:31
加载中...