游客 注册 | 登录
中文 | En

2097 - 数三角形

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

小泽最近最近喜欢上了三角形，因为有三个点，看上去很舒服，而且三角形是很稳定的图形。小泽也有个怪癖就是只喜欢钝角的，因为这样才够奇葩，但是他不这样认为，他认为是种艺术。
现在有N个点在同一个平面上，没有重叠的点，小泽想看看有多少个钝角三角形在点集里面。问题来了，小泽数学不好，数着数着，眼花缭乱了，现在他想邀请强大的你们帮忙算算一共有多少个三角形。

题目输入

有T组数据。
每组数据有一个N（N < 100) 表示有平面里点的个数。
接着每行有两个整数，Xi, Yi，（0 <= Xi, Yi <= 100), 表示第i个点的坐标。

题目输出

对每组数据输出一个整数，表示有多少个钝角三角形

输入/输出样例

输入格式

1
4
1 1
2 2
3 3
1 2

输出格式

2

C语言解答

#include <stdio.h>

int isObtuseTriangle(int, int, int, int, int, int);

int main()
{
	int T, N, points[128][2], i, j, k, count;
	
	scanf("%d", &T);
	while (T--){
		
		scanf("%d", &N);
		if (N < 3){
			printf("%d\n", 0);
			continue;
		}
		for (i = 0; i < N; i++){
			scanf("%d%d", &points[i][0], &points[i][1]);
		}
		
		count = 0;
		for(i = 0; i < N; i++){
			for(j = i + 1; j < N; j++){
				for(k = j + 1; k < N; k++){
					count += isObtuseTriangle(points[i][0],points[i][1],
                                              points[j][0],points[j][1],
											  points[k][0],points[k][1]);
				}
			}
		}
		printf("%d\n", count);
	}
	
	return 0;
}

int isObtuseTriangle(int x1, int y1, int x2, int y2, int x3, int y3)
{
	int sideSquare[3], tmp, slope[2];
	
	if (x1 == x2 && x1 == x3){
		return 0;
	}
	slope[0] = (y2-y1)*(x3-x2);
	slope[1] = (y3-y2)*(x2-x1);
	if (slope[0] == slope[1]){
		return 0;
	}
	
	sideSquare[0] = (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
	sideSquare[1] = (x1-x3)*(x1-x3)+(y1-y3)*(y1-y3);
	sideSquare[2] = (x3-x2)*(x3-x2)+(y3-y2)*(y3-y2);
	
	if (sideSquare[1] > sideSquare[0]){
		tmp = sideSquare[1];
		sideSquare[1] = sideSquare[0];
		sideSquare[0] = tmp;
	}
	if (sideSquare[2] > sideSquare[0]){
		tmp = sideSquare[2];
		sideSquare[2] = sideSquare[0];
		sideSquare[0] = tmp;
	}
	
	if (sideSquare[0] > (sideSquare[1] + sideSquare[2])){
		return 1;
	}
	
	return 0;
}

C++解答

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
const int V = 100 + 5;
int n, T;
int num[V][2];
double len(int i, int j) {
    return sqrt(1.0 * (num[i][0] - num[j][0]) * (num[i][0] - num[j][0]) + 1.0 * (num[i][1] - num[j][1]) * (num[i][1] - num[j][1]));
}
bool is_ok(int i, int j, int k) {
    double a = len(i, j);
    double b = len(j, k);
    double c = len(i, k);
    double Max = max(max(a, b), c);
    double ans;
    if(Max == a)
        ans = (b * b + c * c - a * a) / (2 * b * c);
    else if(Max == b)
        ans = (a * a + c * c - b * b) / (2 * a * c);
    else
        ans = (a * a + b * b - c * c) / (2 * a * b);
    if(ans < 0.0 && fabs(ans) > 1e-6 && ans + 1.0 >= 1e-6)
        return true;
    return false;
}
int main() {
    int i, j, k;
   // FILE *outFile = fopen("a.out", "w");
    //FILE *inFile = fopen("a.in", "r");
   // fscanf(inFile, "%d", &T);
   scanf("%d", &T);
    while(T--) {
        int ans = 0;
      //  fscanf(inFile, "%d", &n);
      scanf("%d", &n);
        for(i = 0; i < n; ++i) {
          //  fscanf(inFile, "%d%d", &num[i][0], &num[i][1]);
            scanf("%d%d", &num[i][0], &num[i][1]);
        }
        for(i = 0; i < n; ++i)
            for(j = i + 1; j < n; ++j)
                for(k = j + 1; k < n; ++k)
                    if(is_ok(i, j, k))
                        ans++;
       // fprintf(outFile, "%d\n", ans);
       printf("%d\n", ans);
    }
}
请先登陆