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对称的。这一点也可以验证这个式子的正确性。

程序写起来就很简单了，代码如下：

#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;
}