PDD7. 数三角形
描述
给出平面上的n个点,现在需要你求出,在这n个点里选3个点能构成一个三角形的方案有几种。输入描述
第一行包含一个正整数n,表示平面上有n个点(n <= 100)输出描述
输出一个数,表示能构成三角形的方案数。示例1
输入:
4 0 0 0 1 1 0 1 1
输出:
4
说明:
4个点中任意选择3个都能构成三角形C 解法, 执行用时: 1ms, 内存消耗: 348KB, 提交时间: 2021-08-29
#include<stdio.h> int main() { int n,i,j,k,num=0; scanf("%d ",&n); int a[2][n]; for(i=0;i<n;i++) { scanf("%d %d",&a[0][i],&a[1][i]); } for(i=0;i<n-2;i++) { for(j=i+1;j<n-1;j++) { for(k=j+1;k<n;k++) { if((a[1][k]-a[1][j])*(a[0][j]-a[0][i])!=(a[0][k]-a[0][j])*(a[1][j]-a[1][i])) { num++; } else; } } } printf("%d\n",num); }
C 解法, 执行用时: 2ms, 内存消耗: 372KB, 提交时间: 2019-07-03
#include<stdio.h> #include<string.h> int n, x[300], y[300], ans; int main() { int i, j, k; scanf("%d", &n); for (i = 0; i<n; i++) { scanf("%d", &x[i]); scanf("%d", &y[i]); } for (i = 0; i<n - 2; i++) for (j = i + 1; j<n - 1; j++) for (k = j + 1; k<n; k++) //内重循环分别是n,n-1和n-2很好的形式 if ((y[i] - y[j])*(x[k] - x[i]) != (y[k] - y[i])*(x[i] - x[j])) //相当于(y[i] - y[j])/(x[i] - x[j])=(y[k] - y[i])/(x[k] - x[i]); 即斜率不一致,不共线 ans++; printf("%d", ans); }
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-10-31
#include<iostream> #include<vector> using namespace std; int main(){ int n ; cin>>n; vector<pair<int, int>> points(n); for(int i = 0;i<n;i++){ cin>>points[i].first>>points[i].second; } int res = 0; for(int i =0;i<n-2;i++){ auto x = points[i]; for(int j = i+1;j<n-1;j++){ auto y = points[j]; for(int k =j+1;k<n;k++){ auto z = points[k]; if((z.second - x.second)*(y.first - x.first) != (y.second - x.second)*(z.first - x.first)){ res++; } } } } cout<<res<<endl; return 0; }
C 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-07-28
#include<stdio.h> #include<string.h> int n, x[300], y[300], ans; int main() { int i, j, k; scanf("%d", &n); for (i = 0; i<n; i++) { scanf("%d", &x[i]); scanf("%d", &y[i]); } for (i = 0; i<n - 2; i++) for (j = i + 1; j<n - 1; j++) for (k = j + 1; k<n; k++) //内重循环分别是n,n-1和n-2很好的形式 if ((y[i] - y[j])*(x[k] - x[i]) != (y[k] - y[i])*(x[i] - x[j])) //相当于(y[i] - y[j])/(x[i] - x[j])=(y[k] - y[i])/(x[k] - x[i]); 即斜率不一致,不共线 ans++; printf("%d", ans); }
C 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2019-07-27
#include <stdio.h> int x[105],y[105]; int main(){ int n; while(~scanf("%d",&n)){ for(int i=0;i<n;i++){ scanf("%d%d",&x[i],&y[i]); } int res=0; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ int x1 = x[j] - x[i], y1 = y[j]-y[i]; for(int k=j+1;k<n;k++){ if(x1*(y[k]-y[i])!=y1*(x[k]-x[i]))res++; } } } printf("%d\n",res); } return 0; }