http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=99&page=show_problem&problem=1731 這是一個數(shù)學題，比較有意思。題意大致是：有2條平行的直線，第一條上面有m個點，第二條上面有n個點。那么連接這寫點能產(chǎn)生m*n
條直線(不包括和原來的執(zhí)行平行的直線)。問這m*n直線最多有多少個內(nèi)交點(意思是不屬于原來m,n個點的交點)...
想來想去，推理了1個多小時才出來正式結(jié)果。感覺比較有意思，寫篇博文記錄下。我先是從反面排除，想了試了好久到最后還是發(fā)現(xiàn)無法
排除干凈。。。最后只能從正面開始求證了。我這樣定義一條執(zhí)行(i，j)，其中i代表在第一條直線中的端點，j代表在第二條直線中的端點。
顯然1 <= i <= m，而且1 <= j <= n。
現(xiàn)在的話只要求出和直線(i，j)相加的直線有多少條，然后對i，j進行累加求和。再對和除以2就能得到答案了。
那么有多少條直線能和直線(i，j）相交了。很顯然，和(i,j)相交的直線的端點必須在其兩側(cè)。意思是在第一條直線中的端點范圍為
[1, i - 1],在第二條直線中的端點范圍為[j + 1, n]，總結(jié)(i - 1) * (n - j) 條直線。但是還有第二種情況,在第一條直線中的端點范圍
為[i + 1, m], 在第二條直線中的端點范圍為[1, j - 1]，總結(jié)(m - i) * (j - 1) 條直線。
總計sum = i * n + i - m -n + j (m - 2 * i + 1) 條直線。
再求
Σsum（j從1到n)得到和式(m*n*n - m*n - n*n + n) / 2，再對這個式子進行i從1到m的累加。因為沒有i了，其效果就是乘以m。
然后最終的和除以2，所以最后的表達式是(m*m*n*n - m*m*n - m*n*n + m*n) / 4。這個式子顯然是關于m,n對稱的。
這一點也可以驗證這個式子的正確性。
程序?qū)懫饋砭秃芎唵瘟耍a如下：
#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;
}