題目鏈接：點擊查看

題目大意：給出n個點，再給出m個詢問，每次詢問給出一個點 x，我們需要回答包括點 x 的直角三角形有多少個

題目分析：題目比較直接，數據也比較小，支持n*n的算法處理，首先我們必須知道，如果要包括點 x 所組成三角形，那么點 x 可以在直角點上，也可以在非直角點上，比較容易想到的方法是離線處理，我們需要分類討論，也就是上述兩個情況，對于每個詢問而言，以點 x 為相對原點，對其余n個點進行極角排序，然后用雙指針保證時間復雜度為O(n)，一個指針固定住一條直角邊，另一個指針去找另一條直角邊上有多少個點，這樣時間復雜度是O(n*m)，解決了點 x 在直角點上的答案，剩下非直角點上的答案我們可以O(n)枚舉直角點，同上利用雙指針計算貢獻，對于有貢獻的點 x 累加答案即可，時間復雜度為大概就是n*m*logn的樣子，不過實現起來比較麻煩，不想多說

還有一種方法比較簡單，但是不太好想，還比較考察代碼功底，就是圍繞著map展開，首先我們要找直角三角形，本質上是要找垂直的兩條邊，換句話說就是需要找兩個向量垂直，將點抽象成向量就簡單多了，和上面大同小異，當點 x 為直角點時，我們記錄下點 x 與 n 個點的向量，最后跑一遍map統計答案即可，當點 x 為非直角點時，一樣O(n)枚舉直角點，O(n)枚舉另一個非直角點，然后直接統計答案就好了，實現起來比較簡單，不過難點不是main函數里，而是在Point結構體內對小于號的重載，因為我們需要的是向量，也就是說需要一個帶斜率的直線，為了方便起見，我們在重載小于號時應該試圖將其歸類，譬如(2,1)和(4,2)雖然數值不一樣，但是代表的都是同一個向量，我們應該將其歸為一類而不是兩類，第一次知道map竟然可以根據小于號將載入的數據重新分類，有了這樣一個方便的性質，在重載好小于號后就可以直接實現main函數里的內容了，比較簡單，具體實現看代碼

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e3+100;struct Point{LL x,y;Point(){}Point(int _x,int _y){x = _x;y = _y;}void input(){scanf("%lld%lld",&x,&y);}Point change()const//將所有的向量都轉換為非負數{if(x<0||x==0&&y<0)return Point(-x,-y);return *this;}bool operator < (const Point &b)const{Point t1=change(),t2=b.change();return t1.x*t2.y<t1.y*t2.x;//利用斜率在map中分類，如果斜率相同則屬于同一個向量}Point operator -(const Point &b)const{return Point(x-b.x,y-b.y);} }point[N];map<Point,int>mp;vector<Point>node;int ans[N];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)point[i].input();for(int i=0;i<m;i++)//查詢點為直角點 {mp.clear();Point temp;temp.input();node.push_back(temp);for(int i=1;i<=n;i++)mp[point[i]-temp]++;for(auto it:mp){Point temp(-it.first.y,it.first.x);ans[i]+=mp[temp]*it.second;}ans[i]/=2;//因為答案累加了兩次，需要除以二}for(int i=1;i<=n;i++)//枚舉n個點分別作為直角點{mp.clear();for(int j=1;j<=n;j++)//枚舉另一個點 {if(i!=j)mp[point[j]-point[i]]++;}for(int j=0;j<m;j++){Point temp=node[j]-point[i];temp=Point(-temp.y,temp.x);ans[j]+=mp[temp];}} for(int i=0;i<m;i++)printf("%d\n",ans[i]);return 0; }

?

總結

以上是生活随笔為你收集整理的Gym - 102361A Angle Beats(几何)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。