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