UVA 10790 How Many Points of Intersection? 组合数学

We have two rows. There are a dots on the top row and b dots on the bottom row. We draw line segments
connecting every dot on the top row with every dot on the bottom row. The dots are arranged in such
a way that the number of internal intersections among the line segments is maximized. To achieve this
goal we must not allow more than two line segments to intersect in a point. The intersection points on
the top row and the bottom are not included in our count; we can allow more than two line segments
to intersect on those two rows. Given the value of a and b, your task is to compute P(a; b), the number
of intersections in between the two rows. For example, in the following gure a = 2 and b = 3. This
gure illustrates that P(2; 3) = 3.

 

 

Input
Each line in the input will contain two positive integers a (0 < a 20000) and b (0 < b 20000).
Input is terminated by a line where both a and b are zero. This case should not be processed. You will
need to process at most 1200 sets of inputs.
Output
For each line of input, print in a line the serial of output followed by the value of P(a; b). Look at the
output for sample input for details. You can assume that the output for the test cases will t in 64-bit
signed integers.
Sample Input
2 2
2 3
3 3
0 0
Sample Output
Case 1: 1
Case 2: 3
Case 3: 9

题意：输入a,b表示上面一条直线有a个点，下面一条直线有b个点，连接上下直线的所有点，问这些线段的交点有几个？题目保证每一个交点只会有两条线段相交于此。

分析：

上面一条直线任取两点和下面一条直线任取两点就会形成一个交点。

所以ans=C(a,2)*C(b,2)。

解毕。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    //freopen("input.txt","r",stdin);
    ll a,b;
    int kase=1;
    while(~scanf("%lld%lld",&a,&b)&&a&&b)
    {
        printf("Case %d: %lld\n",kase++,a*(a-1)*b*(b-1)/4);
    }
    return 0;
}

View Code

 

版权声明：本文为cautx原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/cautx/p/11498848.html