简答题
偏难
#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 <bits/stdc++.h>
using namespace std;
int x[300] = {0}, y[300] = {0};
int main() {
int n, cnt = 0;
cin >> n;
for(int i=0; i<n; i++) {
cin >> x[i] >> y[i];
}
//枚举所有情况
for(int i=0; i<n; i++) {
for(int j=i+1; j<n; j++) {
for(int k=j+1; k<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 << cnt;
return 0;
}</pre>
这道题暂未补解析。