2019 CCPC秦皇岛 A. Angle Beats

题目链接

题目大意：

给你n个点，q次查询，每次查询给出一个点，问这个点可以和平面上的点组成多少个直角三角形。 $n,q\le 2000$

解题思路：

可以分查询点是直角点和非直角点两种情况。 当查询点是直角点的时候，把平面上的点以查询点为源点看作射线，每个射线(x,y)变为(x/gcd(x,y,y/gcd(x,y)),这样就保证了同一射线上的点位置相同（与坐标轴平行的射线要特判），把它们映射到map里，然后依次枚举射线，查询已经在map里面的与该射线垂直的射线个数。 当查询点不是直角点的时候，枚举每一个点作为源点，其他点作为射线映射到map里，对每个查询直接查找有多少个与查询点垂直的射线。 复杂度$O(n^{2}logn)$,觉得慢可以把射线映射成longlong然后存在unordered_map里面假装是$O(n^2)$

#include<bits/stdc++.h> #define ll long long #define lowbit(x) ((x)&(-(x))) #define mid ((l+r)>>1) #define lson rt<<1, l, mid #define rson rt<<1|1, mid+1, r #define P pair<int,int> #define x first #define y second using namespace std; const int maxn = 2e3 + 50; map<P,int> mp; int n, q; P a[maxn], b[maxn]; void init(){ for(int i = 0; i < n; ++i) scanf("%d%d", &a[i].x, &a[i].y); } P get_p(P t){ if(t.x == t.y && t.x == 0) return P(0,0); else if(t.x == 0) return P(0,(t.y > 0) ? 1 : -1); else if(t.y == 0) return P((t.x > 0) ? 1 : -1,0); int temp = __gcd(t.x, t.y); if(temp < 0) temp = -temp; return P(t.x/temp, t.y/temp); } ll ans[maxn]; void sol(){ memset(ans, 0, sizeof ans); for(int i = 0; i < q; ++i){ int x, y; scanf("%d%d", &x, &y); b[i] = P(x,y); mp.clear(); for(int j = 0; j < n; ++j){ P temp = get_p( P( y - a[j].y, a[j].x - x ) ); //cout<<"1 x:"<<temp.x<<" y:"<<temp.y<<endl; if(mp.find(temp) != mp.end()) ans[i] += mp[temp]; temp = get_p( P( a[j].y - y, x - a[j].x ) ); //cout<<"2 x:"<<temp.x<<" y:"<<temp.y<<endl<<endl; if(mp.find(temp) != mp.end()) ans[i] += mp[temp]; mp[get_p(P(a[j].x - x, a[j].y - y))]++; } } for(int i = 0; i < n; ++i){ mp.clear(); for(int j = 0; j < n; ++j){ if(j == i) continue; mp[ get_p(P(a[j].x - a[i].x, a[j].y - a[i].y)) ]++; } for(int j = 0; j < q; ++j){ P temp = get_p( P(b[j].y - a[i].y, a[i].x - b[j].x) ); if(mp.find(temp) != mp.end()) ans[j] += mp[temp]; temp = get_p( P(a[i].y - b[j].y, b[j].x - a[i].x) ); if(mp.find(temp) != mp.end()) ans[j] += mp[temp]; } } for(int i = 0; i < q; ++i){ printf("%I64d\n", ans[i]); } } int main() { while(scanf("%d%d", &n, &q) != EOF){ init(); sol(); } }