怎么会有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("%d", &n);
if (!n) return false;
for (int i=0; i<n; i++)
scanf("%d%d", &x[i], &y[i]);
linen = 0;
return true;
}
int bsearch(int l, int r, double v, int p1, int p)
{
while (l <= r)
{
int mid = (l+r)/2;
if ((x[p1]-x[p])*(x[line[mid].x]-x[p])+(y[p1]-y[p])*(y[line[mid].x]-y[p]) == 0) return mid;
else if (line[mid].k > v) r = mid-1;
else l = mid + 1;
}
return -1;
}
int main()
{
while (in())
{
int ans = 0, t, t1, t2;
for (int i=0; i<n; i++)
{
linen = 0;
for (int j=0; j<n; j++)
{
if (j == i) continue;
line[linen].x = j, line[linen++].k = (x[i]==x[j]) ? INF : ((double)(y[i]-y[j])) / (x[i]-x[j]);
}
sort(line, line + linen, cmp);
for (int j=0; j<linen; j++)
{
if ((t=bsearch(j+1, linen-1, line[j].k==0 ? INF : -1/line[j].k, line[j].x, i)) == -1) continue;
ans++;
t1 = t2 = t;
while (--t1>j && line[t1].k == line[t].k) ans++;
while (++t2<linen && line[t2].k == line[t].k) ans++;
}
}
printf("%d\n", ans);
}
return 0;
}