FZOJ Problem 2110 Star

Problem 2110 Star

Accept: 996 Submit: 2958
Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

Overpower often go to the playground with classmates. They play and chat on the playground. One day, there are a lot of stars in the sky. Suddenly, one of Overpower’s classmates ask him: “How many acute triangles whose inner angles are less than 90 degrees (regarding stars as points) can be found? Assuming all the stars are in the same plane”. Please help him to solve this problem.

Input

The first line of the input contains an integer T (T≤10), indicating the number of test cases.

For each test case:

The first line contains one integer n (1≤n≤100), the number of stars.

The next n lines each contains two integers x and y (0≤|x|, |y|≤1,000,000) indicate the points, all the points are distinct.

Output

For each test case, output an integer indicating the total number of different acute triangles.

Sample Input

1 3 0 0 10 0 5 1000

Sample Output

题意：平面上有n个点，由这n个点中任意三个都可以组成一个三角形，问总共有多少种组合使得得到的三角形的锐角三角形。

思路：穷竭搜索，判断每一种组合下得到的三角形是否为锐角即可，判断锐角的方式：设所要判断的角的两边分别为a,b，斜边c，若a^2+b^2>c^2,即可判断该角为锐角，建立坐标系解析该式，设三角形三顶点的坐标为(x1,y1),(x2,y2),(x3,y3),代入前式化简得

(x1-x2)*(x1-x3)+(y1-y2)*(y1-y3)>0即可。

AC代码：

#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
typedef long long ll;
const int N_MAX = 100 + 5;
int n;
ll x[N_MAX], y[N_MAX];

bool judge(int i,int j,int k) {
    return (x[i] - x[j])*(x[i] - x[k]) + (y[i] - y[j])*(y[i] - y[k])>0;
}

int main() {
    int T;
    scanf("%d",&T);
    while (T--) {
        scanf("%d",&n);

        for (int i = 0; i < n;i++) {
            scanf("%lld%lld",&x[i],&y[i]);
        }
        int num = 0;
        for (int i = 0; i < n;i++) {
            for (int j = 1+i; j < n;j++) {
                for (int k = j + 1; k < n;k++) {
                    if (judge(i, j, k) && judge(j, i, k) && judge(k, i, j)) {
                        num++;
                    }
                }
            }
        }
        printf("%d
",num);
    }
    return 0;
}