翻译2
查看原帖
翻译2
663211
违规用户名DIEIE93J楼主2022/8/5 17:03

贝西从国外长途旅行回来了,农夫约翰想在她的牧场上竖起一面漂亮的“欢迎回家”的横幅,迎接她的到来。横幅将悬挂在长度范围为L1..L2(1<=L1<=L2;L1<=L2<=1500)的电线的两极之间。

牧场的大小为W x H(1<=W<=1000;1<=H<=1000),农夫约翰在每个点都安装了一个带有整数的柱子

在这些(W+1)*(H+1)点中,农夫约翰必须只选择两个点,这两个点将固定他将悬挂旗帜的铁丝网的任一端。

FJ不想干扰他的横幅,因为它挂着,并要求没有职位直接在他在两个选定的职位之间绷紧的铁丝网。

农夫约翰需要你的帮助来找出他可以用多少种方式悬挂旗帜。他知道这个数字很大,32位整数可能不足以计算答案。

考虑下面的示例,W=2,H=1:

横幅大小在2..3范围内。该牧场包含(2+1)(1+1)=6个点,并具有(6 take 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:Len-Len范围内

(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个点中只有两对点是可以接受的悬挂横幅线的候选点。

输入格式

*第1行:四个空格分隔的整数:W、H、L1和L2

输出格式

*第1行:一个整数,表示可能的横幅数量

2022/8/5 17:03
加载中...