首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#13108

几何计数 题目描述 你在坐标纸上标记了 n 个互不相同的点。 现在你想知道:从这些点中任选三个,有多少种选择方式能构成一个真正的三角形? 所谓真正的三角形,是指…

几何计数

题目描述

你在坐标纸上标记了 n 个互不相同的点。

现在你想知道:从这些点中任选三个,有多少种选择方式能构成一个真正的三角形?

所谓真正的三角形,是指三个顶点不共线,即面积大于零的三角形。请计算这个数目。

输入

第一行,一个整数 n,表示点的数量。

接下来 n 行,每行包含两个整数 xi 和 yi ,表示第 i 个点的坐标。

输出

输出一个整数,表示能够构成三角形的三点组合的数量。

数据范围

3≤N≤300,-10^9≤Xi、Yi≤10^9,所有点的坐标互不相同。

输入样例1

3
0 0
2 0
0 -3

输出样例1

1

输入样例2

20
224 433
987654321 987654321
2 0
6 4
314159265 358979323
0 0
-123456789 123456789
-1000000000 1000000000
124 233
9 -6
-4 0
9 5
-7 3
333333333 -333333333
-9 -1
7 -10
-1 5
324 633
1000000000 -1000000000
20 0

输出样例2

1124
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int x[300] = {0}, y[300] = {0}; int main() {     int n, cnt = 0;     cin &gt;&gt; n;     for(int i=0; i&lt;n; i++) {         cin &gt;&gt; x[i] &gt;&gt; y[i];     }     //枚举所有情况     for(int i=0; i&lt;n; i++) {         for(int j=i+1; j&lt;n; j++) {             for(int k=j+1; k&lt;n; k++) {                 // (x2-x1)(y3-y1)-(x3-x1)(y2-y1)不为0                 long long s=(x[j]-x[i])*(y[k]-y[i])-(x[k]-x[i])*(y[j]-y[i]);                 if(s!=0)                     cnt++;             }         }     }     cout &lt;&lt; cnt;     return 0; }</pre>
这道题暂未补解析。