贝西从国外长途旅行回来了,农夫约翰想在她的牧场上竖起一面漂亮的“欢迎回家”的横幅,迎接她的到来。横幅将悬挂在长度范围为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行:一个整数,表示可能的横幅数量