题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6731
题目大意：给n个点，查询q个点，问包含这个点的直角三角形有多少个。
题目思路：
对于一个查询点，要么他是直角三角形的直角顶点，要么是锐角顶点，先把询问离线，然后假设该点做直角顶点，遍历n个点，处理出一个向量，之后查询就是查询与当前向量之积为-1的向量有多少个，对于n个点分别做直角顶点，也是这么整。
坑点：本来打算把符号统一给分子，但是如果分子是0的话，那么就不行了，也就是把符号给忽略了，所以符号要单独处理。
将向量哈希，就可以了。
#include<bits/stdc++.h> #define ll long long using namespace std; struct node { ll x,y,flag; node(){flag = 1;} node(ll a,ll b){x = a;y = b;} node(ll a,ll b,ll c){ x = a;y = b;flag = c; } bool operator < (const node & r)const { return x < r.x; } }a[2005],ask[2005]; ll ans[2005]; //map<node,ll>m; ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; } ll Hash(ll x,ll y,ll z) { ll p = 1e9+7; ll mod = 233333333333333; return (((x*131)+y*p+z*13131))%mod; } //map<pair<pair<ll,ll>,ll>,ll >m; unordered_map<ll,ll>m; int main() { ll n,q; while(~scanf("%lld%lld",&n,&q)){ memset(ans,0,sizeof(ans)); for(ll i=1;i<=n;i++){ scanf("%lld%lld",&a[i].x,&a[i].y); } for(ll i=1;i<=q;i++){ scanf("%lld%lld",&ask[i].x,&ask[i].y); } for(ll i=1;i<=q;i++){ ll sum = 0; m.clear(); for(ll j = 1; j<=n;j++){ ll det_x = a[j].x - ask[i].x; ll det_y = a[j].y - ask[i].y; ll flag = 1; ll num = 0; if(det_x < 0)num++; if(det_y < 0)num++; if(num == 1){ flag = -1; } det_x = abs(det_x); det_y = abs(det_y); ll now = gcd(det_x,det_y); det_x /= now; det_y /= now; //cout<<flag<<" * "<<det_y<<" * "<<det_x<<endl; ll p = Hash(flag,det_y,det_x); //cout<<p<<endl; m[ p ]++; } for(ll j=1;j<=n;j++){ ll det_x = a[j].x - ask[i].x; ll det_y = a[j].y - ask[i].y; ll num = 0,flag = 1; if(det_x < 0)num++; if(det_y < 0)num++; if(num == 1){ flag = -1; } det_x = abs(det_x); det_y = abs(det_y); ll now = gcd(det_x,det_y); det_x /= now; det_y /= now; flag *= -1; ll p = Hash(flag,det_x,det_y); ll p1 = Hash(-flag,det_x,det_y); sum += (m.count(p)) ? m[p]:0; if(det_x==0 || det_y == 0)sum += (m.count(p1)) ? m[p1]:0; } ans[i] += sum/2; } for(ll i=1;i<=n;i++){ m.clear(); ll sum = 0; for(ll j=1;j<=n;j++){ if(i==j)continue; ll det_x = a[j].x - a[i].x; ll det_y = a[j].y - a[i].y; ll flag = 1; ll num = 0; if(det_x < 0)num++; if(det_y < 0)num++; if(num == 1){ flag = -1; } det_x = abs(det_x); det_y = abs(det_y); ll now = gcd(det_x,det_y); det_x /= now; det_y /= now; //node p(flag,det_y,det_x); ll p = Hash(flag,det_y,det_x); m[ p ]++; } for(ll j=1;j<=q;j++){ ll det_x = ask[j].x - a[i].x; ll det_y = ask[j].y - a[i].y; ll flag = 1; ll num = 0; if(det_x < 0)num++; if(det_y < 0)num++; if(num == 1){ flag = -1; } det_x = abs(det_x); det_y = abs(det_y); ll now = gcd(det_x,det_y); det_x /= now; det_y /= now; flag *=-1; ll p = Hash(flag,det_x,det_y); ll p1 = Hash(-flag,det_x,det_y); ans[j] += (m.count(p))?m[p] : 0; if(det_x==0 || det_y == 0) ans[j] += (m.count(p1))?m[p1] : 0; } } for(ll i=1;i<=q;i++){ printf("%lld\n",ans[i]); } } }
