[TIOJ 1205] 直角三角形

作法：

枚舉形成用來當直角的點，所以現在問題變成有 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) ;
    }
}