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("%I64dn", ans[i]);
}
}
int main()
{
while(scanf("%d%d", &n, &q) != EOF){
init(); sol();
}
}

最后

以上就是欣喜八宝粥为你收集整理的2019 CCPC秦皇岛 A. Angle Beats的全部内容，希望文章能够帮你解决2019 CCPC秦皇岛 A. Angle Beats所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。