数三角形

[编程题]数三角形

热度指数：5643 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输入描述:

第一行包含一个正整数n，表示平面上有n个点（n <= 100)
第2行到第n + 1行，每行有两个整数，表示这个点的x坐标和y坐标。(所有坐标的绝对值小于等于100，且保证所有坐标不同）

输出描述:

输出一个数，表示能构成三角形的方案数。

示例1

输入

输出

说明

4个点中任意选择3个都能构成三角形

算法知识视频讲解

Java

牛客703344192号

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        int count = 0;
        //各顶点的x坐标数组和y坐标数组
        for(int i=0;i<n;i++){
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        if(n>=3){
            for(int i=0;i<n-2;i++){
                for(int j=i+1;j<n-1;j++){
                    for(int k=j+1;k<n;k++){
                        //利用三点共线向量公式，若不共线则可构成三角形
                        if((x[i]-x[j])*(y[i]-y[k])!=(x[i]-x[k])*(y[i]-y[j]))
                            count++;
                    }
                }
            }
        }
        System.out.println(count);
    }
}

编辑于 2020-05-05 15:13:30 回复(0)

Java

Mono_Chrome

import java.util.Scanner;

public class Main {


    public static boolean isNoTriangle(int[][] arr, int i, int j, int k) {
        if (arr[i][0] == arr[j][0]) {
            return arr[i][0] == arr[k][0];
        } else if (arr[i][0] == arr[k][0]) {
            return arr[i][0] == arr[j][0];
        } else {
            return (((double)arr[i][1] - (double)arr[j][1]) / ((double)arr[i][0] - (double)arr[j][0])) == (((double)arr[i][1] - (double)arr[k][1]) / ((double)arr[i][0] - (double)arr[k][0]));
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }

        int count = 0;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (!isNoTriangle(arr, i, j, k)) {
                        count++;
                    }
                }
            }
        }
        System.out.println(count);
    }
}

发表于 2019-06-15 19:52:44 回复(0)