uva 10790 - How Many Points of Intersection?

这是一个数学题,比较有意思。题意大致是:有2条平行的直线,第一条上面有m个点,第二条上面有n个点。那么连接这写点能产生mn条直线(不包括和原来的执行平行的直线)。问这mn直线最多有多少个内交点(意思是不属于原来m,n个点的交点)…
想来想去,推理了1个多小时才出来正式结果。感觉比较有意思,写篇博文记录下。我先是从反面排除,想了试了好久到最后还是发现无法排除干净。。。最后只能从正面开始求证了。我这样定义一条执行(i,j),其中i代表在第一条直线中的端点,j代表在第二条直线中的端点。显然1 现在的话只要求出和直线(i,j)相加的直线有多少条,然后对i,j进行累加求和。再对和除以2就能得到答案了。
那么有多少条直线能和直线(i,j)相交了。很显然,和(i,j)相交的直线的端点必须在其两侧。意思是在第一条直线中的端点范围为[1, i - 1],在第二条直线中的端点范围为[j + 1, n],总结(i - 1) * (n - j) 条直线。但是还有第二种情况,在第一条直线中的端点范围为[i + 1, m], 在第二条直线中的端点范围为[1, j - 1],总计(m - i) * (j - 1) 条直线。总计sum = i * n + i - m -n + j (m - 2 * i + 1) 条直线。
再求Σsum(j从1到n)得到和式(mnn - mn - nn + n) / 2,再对这个式子进行i从1到m的累加。因为没有i了,其效果就是乘以m。然后最终的和除以2,所以最后的表达式是(mmnn - mmn - mnn + mn) / 4。这个式子显然是关于m,n对称的。这一点也可以验证这个式子的正确性。

程序写起来就很简单了,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;

int main()
{
long long m, n;
int nCases = 0;

while (cin >> m >> n, m + n != 0)
{
long long a = m * m;
long long b = n * n;
cout << ";Case "; << ++nCases << ";: ";
<< (a * b - a * n - b * m + m * n) / 4 << endl;
}

return 0;
}