JZ高中OJ 1385. 直角三角形

Description

　　二维平面坐标系中有N个点。
　　从N个点选择3个点，问有多少选法使得这3个点形成直角三角形。

Input

　　第一行包含一个整数N(3<=N<=1500)，表示点数。
　　接下来N行，每行包含两个用空格隔开的整数表示每个点的坐标，坐标值在-10^9到10^9之间。
　　每个点位置互不相同。

Output

　　输出直角三角形的数量。

Sample Input

Sample Output

输出1：
1

输出2：
0

输出3：
7

 1 #include <bits/stdc++.h>    
 2 using namespace std;
 3 struct arr{
 4     long long x,y;
 5     int cover;
 6 }tu[1505],f[1505];
 7 int ans[5];
 8 int x[1505],y[1505];
 9 int n,sum;
10 int cmp(arr a,arr b){
11     return a.x*b.y>a.y*b.x;
12 }
13 
14 int rt90(int o){
15     long long t;
16     t=tu[o].x;
17     tu[o].x=tu[o].y;
18     tu[o].y=-t;
19     tu[o].cover+=1; tu[o].cover%=4;
20 }
21 
22 int merge(int x,int y)
23 {
24     if (x!=y){
25         int mid=(x+y)/2;
26         merge(x,mid);
27         merge(mid+1,y);
28         memset(f,0,sizeof(f));
29         int i=x,k=x;
30         int j=mid+1;
31         while (i<=mid&&j<=y){
32             if (tu[i].y*tu[j].x<tu[i].x*tu[j].y){
33                 f[k]=tu[i];
34                 i+=1;
35             } else {
36                 f[k]=tu[j];
37                 j+=1;
38             }
39             k+=1;
40         }
41         while (i<=mid){
42             f[k]=tu[i];
43             i+=1; k+=1;
44         }
45         while (j<=y){
46             f[k]=tu[j];
47             j+=1; k+=1;
48         }
49         for (int i=x;i<=y;i++)
50             tu[i]=f[i];
51     }
52 }
53 
54 int main(){
55     scanf("%ld",&n);
56     for (int i=1;i<=n;i++)
57         scanf("%ld%ld",&x[i],&y[i]);
58     sum=0;
59     for (int i=1;i<=n;i++){
60         for (int j=1;j<=n;j++){
61             tu[j].x=x[j]-x[i];
62             tu[j].y=y[j]-y[i];
63             tu[j].cover=0;
64             if (i==j){
65                 tu[j].x=tu[1].x;
66                 tu[j].y=tu[1].y;
67                 tu[j].cover=tu[1].cover;
68             } else
69             while (!((tu[j].x>0)&&(tu[j].y>=0)))
70                 rt90(j);    
71         }
72         merge(2,n);
73         int j=2;
74         while (j<=n){
75             memset(ans,0,sizeof(ans));
76             int k=j;
77             while ((k<=n)&&(tu[j].y*tu[k].x==tu[j].x*tu[k].y)){
78                 ans[tu[k].cover]+=1;
79                 k+=1;
80             }
81             j=k;
82             for (int o=0;o<=3;o++)
83                 sum+=ans[o]*ans[(o+1)%4];
84         }
85     }
86     printf("%ld",sum);
87 }