枚舉形成用來當直角的點,所以現在問題變成有 n-1 個向量,要問裡面互相垂直的兩個向量的組數有幾組。首先當然是要對這些向量極角排序,但如果直接用 atan2 函式會TLE,他的常數太大了,所以只好自己寫一個爛爛的小於 @@ 。再來只要用雙指標繞一圈就好了,但需要注意在轉的時候的細節,有時候可能會一次轉太多然後就繞回來了,造成誤判之類的。
==============================
後來想想其實直接用 map 把所有向量出現幾次都記錄起來,再直接查詢就好了,比雙指標的方法簡潔多了,但速度慢了很多@@ code 補在下面。
code :
#include<bits/stdc++.h> #define LL long long using namespace std; const int maxn=1500+10 ; struct pt { int x,y,t; bool operator < (const pt &rhs) const { if(x==rhs.x&&y==rhs.y) return 0 ; if(x==0&&y<0) return 1 ; if(rhs.x==0&&rhs.y<0) return 0 ; if(x>0 && rhs.x<=0) return 1 ; if(x<=0 && rhs.x>0) return 0 ; return ((LL)x)*((LL)rhs.y) - ((LL)y)*((LL)rhs.x) > 0LL ; } }a[maxn],b[maxn]; pt operator - (const pt &a,const pt &b){ return (pt){a.x-b.x,a.y-b.y} ; } LL cross(const pt &a,const pt &b) { return ((LL)a.x)*((LL)b.y) - ((LL)a.y)*((LL)b.x) ; } LL dot(const pt &a,const pt &b) { return ((LL)a.x)*((LL)b.x) + ((LL)a.y)*((LL)b.y) ; } main() { int n ; while(scanf("%d",&n)!=EOF && n) { for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y) ; int ans=0 ; for(int z=1;z<=n;z++) { int cnt=-1 ; for(int j=1;j<=n;j++) if(j!=z) { b[++cnt]=a[j]-a[z] ; int g=__gcd(b[cnt].x,b[cnt].y) ; if(g<0) g=-g ; b[cnt].x/=g , b[cnt].y/=g ; } sort(b,b+n-1) ; for(int i=0,j=0 ; i<n-1 ;) { while(cross( (pt){-b[i].y,b[i].x},b[j] ) < 0LL) { j=(j+1)%(n-1) ; if(j==i) break ; } if(-b[i].y!=b[j].x || b[i].x!=b[j].y) { i++ ; continue ; } int i2,j2 ; for(i2=i;i2<n-1 && b[i2].x==b[i].x && b[i2].y==b[i].y;i2++) ; for(j2=j;b[j2].x==b[j].x && b[j2].y==b[j].y;j2=(j2+1)%(n-1)) ; ans+= (i2-i)*( j2>=j ? (j2-j) : (j2-j+n-1) ) ; i=i2 ; j=j2 ; } } printf("%d\n",ans) ; } }
map 版本 :
#include<bits/stdc++.h> #define LL long long #define pii pair<int,int> #define F first #define S second #define mkp(x,y) make_pair(x,y) using namespace std; const int maxn=1500+10 ; pii a[maxn] ; map<pii,int> mp ; main() { int n ; while(scanf("%d",&n)!=EOF && n) { for(int i=1;i<=n;i++) scanf("%d%d",&a[i].F,&a[i].S) ; int ans=0 ; for(int z=1;z<=n;z++) { mp.clear() ; for(int j=1;j<=n;j++) if(j!=z) { int x=a[j].F-a[z].F , y=a[j].S-a[z].S ; int g=__gcd(x,y) ; if(g<0) g=-g ; x/=g ; y/=g ; mp[mkp(x,y)]++ ; } for(auto i : mp) ans+=i.S * mp[mkp(-i.F.S,i.F.F)] ; } printf("%d\n",ans) ; } }
沒有留言:
張貼留言