列表

详情


PDD7. 数三角形

描述

给出平面上的n个点,现在需要你求出,在这n个点里选3个点能构成一个三角形的方案有几种。


输入描述

第一行包含一个正整数n,表示平面上有n个点(n <= 100)
第2行到第n + 1行,每行有两个整数,表示这个点的x坐标和y坐标。(所有坐标的绝对值小于等于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;
}

上一题