传送门
思路
分类讨论
- 当询问的点是直角三角形的直角的顶点时，预处理N个点和询问的点连成的直线的斜率，枚举每个直线，查找有多少个与当前直线垂直的直线（斜率相乘为-1）
- 当询问的点时直角三角形的非直角顶点时，也就是直角顶点在给出的N个点上，这个时候可以预处理N个点之间的直线斜率，然后枚举询问的点和N个点的直线，查找枚举的点上有多少条直线和当前枚举的直线垂直
思路很好想，主要是如何快速，准确的查找到给定斜率的直线有多少条
- 哈希，考虑求斜率分母为0或者分子为0和浮点误差的情况 所以要存以分数的形式存储直线的斜率，根据数据范围设计好哈希函数，然后把哈希出来的数存到map里进行查找，具体思路在代码注释中。
#include<bits/stdc++.h>
#define IOS std::ios_base::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);// 快读using namespace std;
typedef long long ll;
const ll inf = 4e9 + 1;
const int N = 2E3 + 10;
struct ty{
ll x,y;// x = (xa - x2) y = (y1 - y2) k = y/x; 考虑x为0 和y为0的特殊情况 所以分开存储ty (){
};ty (ll a,ll b) : x(a),y(b) {
};ty operator - (const ty & a) const{
return ty{
x - a.x,y - a.y};}
};ll Hush(ty a){
// 要保证斜率相同的直线哈希出来的结果也相同ll g = __gcd( abs(a.x), abs(a.y) );// 如果不约分 斜率实际相同，但是分子分母不同的会被哈希成不同键值a.x /= g;a.y /= g;if(a.x == 0) a.y = 1;// 要特殊的判断 与y轴平行的直线斜率都是无穷大，但是如果y值不同实际哈希结果不同if(a.y == 0) a.x = 1;// 同理if(a.x < 0) a.x = -a.x, a.y = -a.y;// 同理// 哈希函数的设计一定要保证给定的数据范围不会冲突// -2e9 <= a.x <= 2e9 , 2e9 <= a.y <= 2e9 // 设计思路 x,y两个关键字的影响因子要，不同，当其中一个不一样，另一个怎么变化，哈希值都不一样// 所以你可以把x的影响因子设计的很大，一旦x不同，y多大差距都不会出现哈希结果相同// 考虑y的范围, 可以给x的影响因子设计成3e9 这样久能保证定不会冲突了// long long 9e18 哈希值最大 2e9 * 4e9 + 2e9 = 8e18return a.x * inf + a.y;
}unordered_map<ll,int> mp;
unordered_map<ll,int> all_mp[N];
ty a[N];
ll k[N];int main(){
IOSint n,m; cin >> n >> m;for(int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y;for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j) if(j != i) ++all_mp[i][Hush(a[i] - a[j])];while(m--){
long long ans = 0;ty t; cin >> t.x >> t.y;for(int i = 1; i <= n; ++i) ++mp[Hush(a[i] - t)];// 这一步 很关键，因为Hush很耗时间，且 这个斜率的查找会用到两次，所以提前存储for(int i = 1; i <= n; ++i) k[i] = Hush({
a[i].y - t.y, t.x - a[i].x});// for(int i = 1; i <= n; ++i)// 直角在询问的点上if(mp.count(k[i])) ans += mp[k[i]];ans >>= 1;// 上面答案会被重复记录一次for(int i = 1; i <= n; ++i) // 直角不在询问的点上if(all_mp[i].count(k[i])) ans += all_mp[i][k[i]];cout << ans << '\n';mp.clear();}return 0;
}
- 不用哈希，直接用分数形式的斜率进行排序，然后二分查找指定斜率的直线个数,细节看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2E3 + 10;
struct ty{
ll x,y;ty (){
};ty (ll a,ll b) : x(a), y(b){
};bool operator < (const ty &a)const {
return y * a.x < a.y * x;}ty operator - (const ty &a) const{
return ty{
x - a.x, y - a.y};}
};//调整斜率保证排序正确
void spj(ty & a){
//如 0/3 2/3 0/-3 2/3 排序结果不同。但0/3 和 0/-3 斜率实际上是一样的if(a.x == 0) a.y = 1;//如 3/0 2/3 -3/0 2/3 排序结果不同。但3/0 和 -3/0 斜率实际上是一样的if(a.y == 0) a.x = 1;// 保证排序正确分母a.x一定不能为负数//如 -2/3 2/3 2/-3 2/3 排序结果不同。但-2/3 和 2/-3 斜率实际上是一样的if(a.x < 0) a.x = -a.x,a.y = -a.y;
}ty a[N], mp[N],amp[N][N];int main(){
int n,m; cin >> n >> m;for(int i = 1; i <= n; ++i)cin >> a[i].x >> a[i].y;for(int i = 1; i <= n; ++i){
int cnt = 0;for(int j = 1; j <= n; ++j){
if(i == j) continue;ty p = a[i] - a[j];spj(p);amp[i][++cnt] = p;}sort(amp[i] + 1,amp[i] + n);}while(m--){
long long ans = 0;ty t; cin >> t.x >> t.y;for(int i = 1; i <= n; ++i){
ty p = a[i] - t;spj(p);mp[i] = p;}sort(mp + 1,mp + n + 1);for(int i = 1; i <= n; ++i){
ty p{
a[i].y - t.y, t.x - a[i].x};// (y1 - y2)/(x1 - x2) * k= - 1;spj(p);ans += upper_bound(mp + 1,mp + n + 1,p) - lower_bound(mp + 1,mp + n + 1,p);}ans >>= 1;for(int i = 1; i <= n; ++i){
ty p{
a[i].y - t.y, t.x - a[i].x};spj(p);ans += upper_bound(amp[i] + 1,amp[i] + n,p) - lower_bound(amp[i] + 1,amp[i] + n ,p);}cout << ans << '\n';}return 0;}