贝西正要从一趟长途旅行中回来,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对点中只有两对点可以作为悬挂横幅线的候选点。