UC知道题目直角三角形
来源：百度知道 编辑：UC知道 时间：2024/06/17 00:31:55
我现在都超时
直角三角形
Time Limit:7000MS Memory Limit:65536K
Total Submit:81 Accepted:13
Description
给你N个座标平面上的点，请问总共可形成多少个直角三角形呢？
Input
输入档可能包含多笔测试资料。
每笔测试资料的第一列有一个正整数N，代表平面上的点数(3<=N<=1500)。当N=0的时候代表输入结束。
接下来有N列每列有一个座标，座标值都是介於 -10^9以及10^9之间的整数。
同一个座标上不会有两个点。
Output
请输出直角三角形的个数。
Sample Input
3
4 2
2 1
1 3
4
5 0
2 6
8 6
5 7
5
-1 1
-1 0
0 0
1 0
1 1
0
Sample Output
1
0
7
O(n^4)大概会过不了,因为n最大是1500
如果用斜率是可行,但遇到斜率无限大该如何?
怎么会有O(n^4)这么差劲的算法…… 最朴素的都是O(n^3)， 取完所有3个点的组合方式， 判断下是否直角， 不就ok了？
较优算法应该是这样
1. 求所有两点组合的直线斜率， O(n^2)
2. 对上述斜率排序, 得到长度为n^2的斜率数组，O(n^2log(n^2))
3. 对于每个斜率k， 二分搜索-1/k这个斜率是否存在， 如果存在， 看是否可以构成三角形，O(n^2log(n^2))
就是这样了， 总的时间复杂度等于最大的一个 O(n^2log(n^2))
n是1500的话， 也就千万数量级， 肯定可以过
对于斜率无限大，可以特殊处理下， 因为 “座标值都是介於 -10^9以及10^9之间的整数” 所以最大斜率不会超过10^9. 你用20亿当作无限大就可以了。
修正一下， 上述算法可能会退化到n^4的情况， 以下算法应该不会
1. 遍历每个点， 分别假设每个点为直角三角形的顶点
2. 对于每个1中的顶点，找出所有经过它的直线（n-1条），并按斜率排序
3. 对于每条直线line， 二分搜索这n-1条直线， 找出与它垂直的直线linex，并且往前往后寻找与linex斜率相同的直线。
表述可能不大清楚 附ac的程序
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1503, INF = 2000000000;
int n, x[MAXN], y[MAXN], linen;
struct Line { int x; double k; };
Line line[MAXN];
bool cmp(const Line &a, const Line &b)
{
return a.k < b.k;
}
bool in()
{
scanf("%