[55]数三角形-拼多多2018秋

1.题目描述

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

• 输入描述:
  第一行包含一个正整数 n，表示平面上有 n 个点（n <= 100) 第 2 行到第 n + 1 行，每行有两个整数，表示这个点的 x 坐标和 y 坐标。(所有坐标的绝对值小于等于 100，且保证所有坐标不同）
• 输出描述:
  输出一个数，表示能构成三角形的方案数。
• 输入:

  4
  0 0
  0 1
  1 0
  1 1
  

• 输出:

  4
  

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

2.题目解析

穷举法
如何遍历数组中不重复的三点？

如果三点不共线, 就可以构成三角形
判断三点是否共线：两条线段斜率是否相等？(x1-x2)*(y1-y3) = (y1-y2)*(x1-x3)

3.参考答案

#include <cstdio>
using namespace std;
struct Point {
  int x;
  int y;
};

int main() {
  int n;
  scanf("%d", &n);
  
  Point a[n];
  for (int i = 0; i < n; ++i) {
    scanf("%d %d", &a[i].x, &a[i].y);
  }
  int res = 0;
  for (int i = 0; i < n; ++i) {// 遍历第一个点
    for (int j = i + 1; j < n; ++j) { // 遍历第二个点
      for (int k = j + 1; k < n; ++k) { // 遍历第三个点
        // 判断是否共线
        if ((a[j].x - a[i].x) * (a[k].y - a[i].y) !=
            (a[k].x - a[i].x) * (a[j].y - a[i].y)) {
          ++res;
        }
      }
    }
  }
  printf("%d\n", res);
}

牛客题目