本文共 3955 字，大约阅读时间需要 13 分钟。
Description
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
Sample Input
130 010 05 1000
Sample Output
1 套一个锐角三角形的性质就可以了 两边平方和大于第三边的平方和 开始用第一种方法来做 比较耗时 后来看了高端玩家是怎么循环的 第二种方法的耗时大大的降低 way1
#include #include #include #include #include #include #include #include #include using namespace std;#define FIN freopen("input.txt","r",stdin);#define FOUT freopen("output.txt","w",stdout);#define INF 0x3f3f3f3f#define INFLL 0x3f3f3f3f3f3f3f#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1typedef long long LL;typedef pair PII;const int MX = 100 + 5;struct Point{ double x, y;}P[MX];bool check(int i, int j, int k){ if(i == j || i == k || j == k) return false; double len1 = (P[i].x - P[j].x)*(P[i].x - P[j].x) + (P[i].y - P[j].y)*(P[i].y - P[j].y); double len2 = (P[i].x - P[k].x)*(P[i].x - P[k].x) + (P[i].y - P[k].y)*(P[i].y - P[k].y); double len3 = (P[j].x - P[k].x)*(P[j].x - P[k].x) + (P[j].y - P[k].y)*(P[j].y - P[k].y); len1 = sqrt(len1); len2 = sqrt(len2); len3 = sqrt(len3); if(len1 * len1 + len2 * len2 > len3 * len3) if(len1 * len1 + len3 * len3 > len2 * len2) if(len3 * len3 + len2 * len2 > len1 * len1) return true; return false;}int main(){ //FIN int t; while (~scanf ("%d", &t)){ while (t--){ int n; scanf ("%d", &n); for (int i = 0; i < n; i ++) scanf ("%lf%lf", &P[i].x, &P[i].y); int cnt = 0; for (int i = 0; i < n; i ++){ for(int j = 0; j < n ; j ++){ for(int k = 0; k < n; k ++){ if(check(i, j, k)) cnt ++; } } } printf ("%d\n",cnt/6); } } return 0;}
way2
#include #include #include #include #include #include #include #include #include using namespace std;#define FIN freopen("input.txt","r",stdin);#define FOUT freopen("output.txt","w",stdout);#define INF 0x3f3f3f3f#define INFLL 0x3f3f3f3f3f3f3f#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1typedef long long LL;typedef pair PII;const int MX = 100 + 5;struct Point{ double x, y;}P[MX];bool check(int i, int j, int k){ double len1 = (P[i].x - P[j].x)*(P[i].x - P[j].x) + (P[i].y - P[j].y)*(P[i].y - P[j].y); double len2 = (P[i].x - P[k].x)*(P[i].x - P[k].x) + (P[i].y - P[k].y)*(P[i].y - P[k].y); double len3 = (P[j].x - P[k].x)*(P[j].x - P[k].x) + (P[j].y - P[k].y)*(P[j].y - P[k].y); len1 = sqrt(len1); len2 = sqrt(len2); len3 = sqrt(len3); if(len1 * len1 + len2 * len2 > len3 * len3) if(len1 * len1 + len3 * len3 > len2 * len2) if(len3 * len3 + len2 * len2 > len1 * len1) return true; return false;}int main(){ //FIN int t; while (~scanf ("%d", &t)){ while (t--){ int n; scanf ("%d", &n); for (int i = 0; i < n; i ++) scanf ("%lf%lf", &P[i].x, &P[i].y); int cnt = 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(check(i, j, k)) cnt ++; } } } printf ("%d\n",cnt); } } return 0;}
转载于:https://www.cnblogs.com/Hyouka/p/5790925.html