当前位置：首页 > news >正文

HDU-6731 Angle Beats 计算几何直角三角形个数

news 来源：原创 2023/6/7 4:29:25

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6731

题意：n个点，m次查询，每次给你一个点，从n个点挑出两个能组成多少直角三角形

题解：假设询问的是点p，直角可能是p也可能是其他两点的某个，当是其他点时，我们枚举n个点，让他作为直角，这样就能确定出一条直线，在直线上的点数就是当前能构成直角三角形的个数，如果在通过枚举的话肯定是不行的，所以我们预处理出每两个点直线方程，k和b，哈希保存下来(这个直接用long double就可以了，之前用的用1e9+7来哈希，但是超时了)，然后就可以二分确定下当前的数目，如果直角是p这个点，那么也是相同的处理方法，但是这样得到的数目要除2，因为多算了一半，唉...

#include <bits/stdc++.h>
#include <tr1/unordered_map>
using namespace std;
typedef long long ll;
const ll mod = 2e9 + 7;
const ll jz = 100007;
const int N = 2010;
struct node {ll x, y;
}p[N];
int n, m;
tr1::unordered_map<ll, ll> mp;
vector<long double> v[N];
ll num[N];vector<long double> vp;
ll nump;
/*
ll ksm(ll x, ll y) {
//    if(mp[x]) return mp[x];ll res = 1;while(y) {if(y & 1) res = res * x % mod;y >>= 1;x = x * x % mod;}return res;
}
*/
int main() {long double k, b;ll x, y;ll res1, res2;long double cnt;while(~scanf("%d %d", &n, &m)) {for(int i = 1; i <= n; i++) {scanf("%lld %lld", &p[i].x, &p[i].y);v[i].clear();num[i] = 0;}for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {if(i == j) continue;if(p[i].x == p[j].x) num[i]++;else {k = (long double)(p[i].y - p[j].y) / (p[i].x - p[j].x);b = p[i].y - k * p[i].x;v[i].push_back(k * mod + b);}}sort(v[i].begin(), v[i].end());}while(m--) {scanf("%lld %lld", &x, &y);res1 = res2 = 0;nump = 0;vp.clear();for(int i = 1; i <= n; i++) {if(y == p[i].y) res1 += num[i];else {k = (long double)(p[i].x - x) / (y - p[i].y);b = p[i].y - k * p[i].x;cnt = k * mod + b;res1 += upper_bound(v[i].begin(), v[i].end(), cnt) - lower_bound(v[i].begin(), v[i].end(), cnt); }if(p[i].x == x) nump++;else {k = (long double)(p[i].y - y) / (p[i].x - x);b = p[i].y - k * p[i].x;cnt = k * mod + b;vp.push_back(cnt);}}sort(vp.begin(), vp.end());//    cout << nump << endl;for(int i = 1; i <= n; i++) {if(y == p[i].y) res2 += nump;else {k = (long double)(p[i].x - x) / (y - p[i].y);b = y - k * x;cnt = k * mod + b;res2 += upper_bound(vp.begin(), vp.end(), cnt) - lower_bound(vp.begin(), vp.end(), cnt); }}//    cout << res1 << " " << res2 << endl;printf("%lld\n", res1 + res2 / 2);}}return 0;
}
[ Copy to Clipboard ]    [ Save to File]

相关文章：