Angle Beats
$$ Time Limit: 4000 ms \quad Memory Limit: 1048576 kB $$
题意
给出 $n$ 个初始点以及 $q$ 次询问，每次询问给出一个询问点 $Q$，求包括 $Q$ 点的直角三角形有多少个。保证 $n+q$ 个点都不重复。
思路
- 对于每次询问，当 $Q$ 为直角点时，以 $Q$ 为原点，对 $n$ 个点做象限极角排序，然后用双指针 $L$、 $R$ 维护直角三角形的个数。 $L$ 指针用来枚举其中的一条直角边， $R$ 指针用来寻找在另一条直角边上的点有多少个，每次找 $QL$ 这条边逆时针方向的另一条边$QR$。所以当 $L$ 往逆时针转动时，$R$ 也会往逆时针转动，那么就可以用双指针直接维护出来了，特别注意一下多个点在同一条直线上的情况就可以了。
- 若 $Q$ 不是直角点时，可以离线处理，把 $n+q$ 个点全部存出来，然后枚举以 $n$ 个初始点为直角点时，对哪些的 $Q$ 点有贡献，维护方法同上。
最后的复杂度为 $O\left(qnC_1 + n(n+q)C_2\right)$，$C_1、C_2$ 取决于在枚举直角点为原点后，到原点在同一条直线上的点数量。 我试过把 $n+q$ 个节点全部提取出来，然后暴力枚举每个点为直角点的情况，但是这样复杂度会 $T$。
1#include<bits/stdc++.h> 2using namespace std; 3typedef long long ll; 4typedef unsigned long long ull; 5const int maxn = 1e4+10; 6 7struct Point { 8 ll x, y; 9 int id; 10} p[maxn], be[maxn]; 11int n, m; 12int ans[maxn]; 13 14int cmp1(Point a, Point b) { 15 ll d = a.x*b.y - b.x*a.y; 16 if(d == 0) { 17 return a.x<b.x; 18 } else { 19 return d>0; 20 } 21} 22int Qua(Point a) { 23 if(a.x>0 && a.y>=0) return 1; 24 if(a.x<=0 && a.y>0) return 2; 25 if(a.x<0 && a.y<=0) return 3; 26 if(a.x>=0 && a.y<0) return 4; 27} 28 29int cmp(Point a, Point b) { 30 if(Qua(a) == Qua(b)) return cmp1(a, b); 31 else return Qua(a)<Qua(b); 32} 33 34ll check(Point a, Point b) { 35 return a.x*b.x + a.y*b.y; 36} 37 38ll chaji(Point a, Point b) { 39 return a.x*b.y - b.x*a.y; 40} 41 42ll work(Point pp) { 43 for(int i=1; i<=n; i++) { 44 p[i] = be[i]; 45 p[i].x -= pp.x; 46 p[i].y -= pp.y; 47 } 48 p[0] = pp; 49 sort(p+1, p+1+n, cmp); 50 for(int j=1; j<=n; j++) { 51 p[j+n] = p[j]; 52 } 53 ll ans = 0; 54 int R = 2; 55 for(int L=1; L<=n; L++) { 56 while(R<=2*n) { 57 if(chaji(p[L], p[R]) < 0) break; 58 if(check(p[L], p[R]) <= 0) break; 59 R++; 60 } 61 int tR = R; 62 while(tR<=2*n) { 63 if(chaji(p[L], p[tR]) <= 0) break; 64 if(check(p[L], p[tR]) != 0) break; 65 ans++; 66 tR++; 67 } 68 } 69 return ans; 70} 71 72int main(){ 73 // freopen("in", "r", stdin); 74 while(~scanf("%d%d", &n, &m)) { 75 int all = 0; 76 for(int i=1; i<=n; i++) { 77 all++; 78 int x, y; 79 scanf("%d%d", &x, &y); 80 p[all].x = x, p[all].y = y, p[all].id = 0; 81 be[all] = p[all]; 82 } 83 for(int i=1; i<=m; i++) { 84 all++; 85 int x, y; 86 scanf("%d%d", &x, &y); 87 p[all].x = x, p[all].y = y, p[all].id = i; 88 be[all] = p[all]; 89 ans[i] = work(p[all]); 90 } 91 for(int i=1; i<=n; i++) { 92 for(int j=1; j<=all; j++) { 93 p[j] = be[j]; 94 } 95 p[0] = be[i]; 96 int flag = 0; 97 for(int j=1; j<=all; j++) { 98 if(p[j].x == p[0].x && p[j].y == p[0].y) flag = 1; 99 if(flag) p[j] = p[j+1]; 100 p[j].x -= p[0].x; 101 p[j].y -= p[0].y; 102 } 103 104 int nn = all-1; 105 sort(p+1, p+1+nn, cmp); 106 for(int j=1; j<=nn; j++) { 107 p[j+nn] = p[j]; 108 } 109 int R = 2; 110 for(int L=1; L<=nn; L++) { 111 int id = 0; 112 if(p[0].id) id = p[0].id; 113 if(p[L].id) id = p[L].id; 114 while(R<=2*nn) { 115 if(chaji(p[L], p[R]) < 0) break; 116 if(check(p[L], p[R]) <= 0) break; 117 R++; 118 } 119 int tR = R; 120 while(tR<=2*nn) { 121 if(chaji(p[L], p[tR]) <= 0) break; 122 if(check(p[L], p[tR]) != 0) break; 123 if(id == 0) { 124 if(p[tR].id) ans[p[tR].id]++; 125 } else { 126 if(p[tR].id == 0) ans[id]++; 127 } 128 tR++; 129 } 130 } 131 } 132 for(int i=1; i<=m; i++) { 133 printf("%d\n", ans[i]); 134 } 135 } 136 return 0; 137}