63. 三角形是一个永不过时的话题

63. 三角形是一个永不过时的话题

题目描述

    欢迎参加程序设计竞赛~

    程序设计竞赛中有着很多有意思的问题，其中，与三角形有关的问题就经常出现。今天你要解决的，就是其中最简单的一个问题：

    给定平面直角坐标系上的 N 个点，保证这 N 个点中任意三点都不共线。求任意三点能够构成的三角形中，面积最大的三角形的面积。

输入：

    输入的第一行是一个整数 T（1 <= T <= 10），表示一共有 T 组用例。

    每组用例的第一行为一个整数 N（3 <= n <= 100），表示平面上点的个数。
    接下来的 N 行，每行包含两个用空格隔开的整数 Xi 和 Yi（-1000 <= Xi, Yi <= 1000），表示第 i 个点的坐标（Xi, Yi）。

输出：

    每组用例输出一个数，表示最大的三角形的面积，结果保留一位小数。

输入样例：
2
4
-1 1
1 1
1 -1
-1 -1
3
-1 -1
3 0
0 0

输出样例：
2.0
1.5

【分析】：

感觉很难，只能想到非常愚蠢的暴力做法！用三重循环遍历所有的点来求最大值。三角形面积因为给了坐标，可以用叉乘来计算

【代码】：

#include <stdio.h>
#include <math.h>
int main(void) {
	int T = 0;
	scanf("%d", &T);
	for (; T > 0; T--) {
		int n = 0; double S = 0;
		scanf("%d", &n);
		int x[120], y[120];
		for (int i = 0; i < n; i++) scanf("%d %d", &x[i], &y[i]);
		for(int i=0;i+2<n;i++)
			for(int j=i+1;j+1<n;j++)
				for (int k = i + 2; k < n; k++) {
					double t =fabs( ((x[j] - x[i]) * (y[k] - y[i]) - (x[k] - x[i]) * (y[j] - y[i]))*0.5 );
					S = S > t ? S : t;
				}
		printf("%.1f\n", S);
	}
}