題目大意：有n個點(x,y<=10^9，n<=1500)，求出這n個點組成的三角形是直角三角形的方案數(shù)。

【做法1】

暴力枚舉直角三角形的三個點，再用勾股定理判斷是否是直角。時間復(fù)雜度O(n^3)。

【做法2】

假設(shè)原點也是點，則可以按照x軸正半軸旋轉(zhuǎn)到每個點所需的角度排序，然后用單調(diào)隊列掃描一遍。

如下圖所示：

那么我們可以枚舉每個點A作為直角三角形斜邊對應(yīng)的點，也就是直角點，那么其他點B的坐標(biāo)就要變成——(B.x-A.x,B.y-A.y)，然后按上面的方法算就可以了。

則時間復(fù)雜度O(n^2logn)，編程復(fù)雜度高，容易錯。

【做法3】

考慮到直角是90度，那么，將直角邊上的一點旋轉(zhuǎn)90度，便與另一條線重合。于是我們可以把每個點都記住它原始的象限，再每次旋轉(zhuǎn)90度，旋轉(zhuǎn)到第一象限內(nèi)。然后按照其斜率排序，找出其斜率相同的點，則這些點都在同一直線上。統(tǒng)計每個象限內(nèi)的點的個數(shù)，又因為1,2象限，2,3象限，3,4象限和4，1象限是相鄰的。根據(jù)乘法原理和加法原理，將每個象限內(nèi)的點的個數(shù)按上面的方法計算即可。具體看程序：

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> using namespace std; #define Maxn 1510 typedef long long LL; struct Point{int x,y;int p;double k;void turn(){ x=-x; swap(x,y); }//將點“逆”時針旋轉(zhuǎn)90度 void calc_k()//計算斜率 {if(x==0) k = 1000000001;else k = (0.0+y)/(0.0+x);} }; bool cmp(Point x,Point y){return x.k<y.k;}//按照斜率排序 bool equ(double x,double y)//實數(shù)判斷是否相等 {if(x>y) return 0;if(y>x) return 0;return 1; } LL f[10],ans; Point a[Maxn],b[Maxn]; int n; int main() {scanf("%d",&n);int x,y;for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);for(int t=1;t<=n;t++)//枚舉直角點，以這點建立平面直角坐標(biāo)系 {swap(a[n],a[t]);//則a[n]為直角點 memset(b,0,sizeof(b));for(int i=1;i<n;i++){b[i].x = x = a[i].x-a[n].x;b[i].y = y = a[i].y-a[n].y;if(x>=0 && y<0){b[i].turn(); b[i].turn(); b[i].turn();b[i].p = 4;}else if(x<0 && y<=0){b[i].turn(); b[i].turn();b[i].p = 3;}else if(x<=0 && y>0){b[i].turn();b[i].p = 2;}else b[i].p = 1;b[i].calc_k();}sort(b+1,b+n,cmp);//排序 int i,j;for(i=1;i<n;)//統(tǒng)計每個象限的點的個數(shù) {memset(f,0,sizeof(f));for(j=i;j<n && equ(b[i].k,b[j].k);j++);for(int k=i;k<j;k++) f[b[k].p]++;i = j;ans += f[1]*f[2]+f[2]*f[3]+f[3]*f[4]+f[4]*f[1];}swap(a[n],a[t]);}printf("%lld\n",ans);return 0; }這個做法簡單，不易錯。時間復(fù)雜度也是O(n^2logn)。

轉(zhuǎn)載于:https://www.cnblogs.com/ouqingliang/p/9245257.html

總結(jié)

以上是生活随笔為你收集整理的求直角三角形的个数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。