2019CCPC秦皇岛赛区 - A. Angle Beats

题意：

给定 n 个点坐标，再有 q 个询问，每次询问给一个点 A，求满足 ( A, B, C ) 三点构成直角三角形的无序点对 ( B, C ) 的个数，其中 B，C 为已知点。(n, q <= 2e3)

链接：

https://vjudge.net/problem/HDU-6731

解题思路：

首先解决判定构成直角的问题，直角即垂直，即斜率相乘为 -1，若以 $\frac{a}{b}$ 的形式代表斜率，则对于某两点确定的斜率，只需查对应的 $\frac{-b}{a}$ 有多少个。听说会卡时限，这里我直接用哈希表查询。
然后考虑如何统计答案。对于一个询问点 A，有两种情况，①：A 为直角顶点，此时枚举直角三角形的第二个点得到一个斜率 k1，再查询经过 A 的满足 k2 = $\frac{-1}{k1}$ 的直线条数，显然我们需要预先将 A 与 n 个点的斜率放进哈希表，这部分每种三角形会被计算两次，统计后除以 2 即可；②：A 不是直角顶点，此时枚举直角顶点 B，然后查询经过 B 的直线条数，这部分可以预处理出每个点的哈希表。
至于细节问题，就是斜率表示的 $\frac{a}{b}$，统一斜率为 0 的表示为 $\frac{0}{1}$，斜率不存在表示为 $\frac{1}{0}$，其他情况需要让分数化为最简分数，并且统一负斜率的负号在分子或分母，最后用一个大于 2e9 的 base 就可以丢进哈希表了。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define sz(a) ((int)a.size())
#define mem(a, b) memset(a, b, sizeof a)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define gmid (l + r >> 1)
const int maxn = 2e3 + 5;
const int maxm = 1e6 + 5;
const int mod = 2333;
const int inf = 0x3f3f3f3f;
struct Hash{
struct Has{
int num, nxt; ll h;
} has[maxn];
int head[mod], cnt;
int rub[maxn], top;
void init(){
while(top) head[rub[top--]] = 0; cnt = 0;
}
void add(ll h){
int u = h % mod; u = u < 0 ? -u : u;
for(int i = head[u]; i; i = has[i].nxt){
if(has[i].h == h) { ++has[i].num; return; }
}
rub[++top] = u;
has[++cnt] = { 1, head[u], h }, head[u] = cnt;
}
int get(ll h){
int u = h % mod; u = u < 0 ? -u : u;
for(int i = head[u]; i; i = has[i].nxt){
if(has[i].h == h) return has[i].num;
}
return 0;
}
} hi[maxn];
const ll base = 2e9 + 7;
int xi[maxn], yi[maxn];
pii pi[maxn];
int n, q;
int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}
pii cal(int a, int b){
if(a == 0) b = 1;
else if(b == 0) a = 1;
else{
int d = gcd(abs(a), abs(b));
a /= d, b /= d;
if(b < 0) a = -a, b = -b;
}
return {a, b};
}
int main(){
//	ios::sync_with_stdio(0); cin.tie(0);
while(scanf("%d%d", &n, &q) != EOF){
for(int i = 1; i <= n; ++i) scanf("%d%d", &xi[i], &yi[i]);
for(int i = 1; i <= n; ++i){
hi[i].init();
for(int j = 1; j <= n; ++j){
if(i == j) continue;
pii tmp = cal(xi[i] - xi[j], yi[i] - yi[j]);
hi[i].add(tmp.first * base + tmp.second);
}
}
int p = n + 1;
while(q--){
int x, y; scanf("%d%d", &x, &y);
hi[p].init();
int ret1 = 0, ret2 = 0;
for(int i = 1; i <= n; ++i){
pi[i] = cal(x - xi[i], y - yi[i]);
hi[p].add(pi[i].first * base + pi[i].second);
}
for(int i = 1; i <= n; ++i){
pii tmp = pi[i];
if(tmp.first == 0 && tmp.second == 1 || tmp.first == 1 && tmp.second == 0);
else{
if(tmp.first > 0) tmp.second = -tmp.second;
else tmp.first = -tmp.first;
}
ret1 += hi[i].get(tmp.second * base + tmp.first);
ret2 += hi[p].get(tmp.second * base + tmp.first);
}
printf("%dn", ret1 + ret2 / 2);
}
}
return 0;
}

最后

以上就是典雅硬币为你收集整理的2019CCPC秦皇岛赛区 - A. Angle Beats的全部内容，希望文章能够帮你解决2019CCPC秦皇岛赛区 - A. Angle Beats所遇到的程序开发问题。

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