2019秦皇岛A - Angle Beats Gym - 102361A（极角排序，多少个直角三角形）

Given n points P1,P2,⋯,Pn on 2D plane and q queries. In i-th query, a point Ai is given, and you should determine the number of tuples (u,v) that 1≤u<v≤n and Ai,Pu,Pv form a non-degenerate right-angled triangle.

Input
The first line contains two positive integers n,q (2≤n≤2000,1≤q≤2000), denoting the number of given points and the number of queries.

Next n lines each contains two integers xi,yi (|xi|,|yi|≤109), denoting a given point Pi.

Next q lines each contains two integers xi,yi (|xi|,|yi|≤109), denoting a query point Ai.

It is guaranteed that the input n+q points are all pairwise distinct.

Output
Output q lines each contains a non-negative integer, denoting the answer to corresponding query.

Example
Input
4 2
0 1
1 0
0 -1
-1 0
0 0
1 1
Output
4
3
Note
For query (0,0), the 4 right-angled triangles are

{(0,0),(0,1),(1,0)}
{(0,0),(0,1),(−1,0)}
{(0,0),(0,−1),(1,0)}
{(0,0),(0,−1),(−1,0)}
For query (1,1), the 3 right-angled triangles are

{(1,1),(0,1),(1,0)}
{(1,1),(0,1),(0,−1)}
{(1,1),(1,0),(−1,0)}

题意： 给出n个点，q次询问，每次询问给出一个点，问这个给出的点和原有的点可以组成多少个三角形。
思路：

一开始甚至没有想到暴力的解法，提醒才发现，已知一个向量（斜率），可以O(1)找出垂直的向量。算斜率的话，得用map和gcd。但是，本题卡常。如果同时用了map和gcd肯定会被卡掉。于是得换成向量，省去这个gcd。方法是，重载向量结构体的时候直接用斜率进行比较。
有两种可能：这个给出点在直角上，这个给出点是斜边上点。
本题和HDU - 5784有相似之处。不同的是，这道题算的是直角，而且有个固定的询问点。hdu那道题求的是锐角，点一开始全部给出了。这道题求直角，先天的优势就是算出共线（向量）后可以o(1)直接求出垂直的值。也可以极角排序求。如果这个点是直角，以这个点建立极角，然后直接找加上PI/2的，本题实际上就是用map进行斜率排序代替相对角度排序。不过如果你用角度排序，貌似可以直接开数组求了，会快很多吧。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <map>

using namespace std;

const int maxn = 2e3 + 7;
const double eps = 1e-9;

typedef long long ll;
struct Point
{
    ll x,y;
    Point(){}
    Point(ll a,ll b):x(a),y(b){}
    Point Base() const
    {
        if(x < 0 || (x == 0 && y < 0))
        {
            return Point(-x,-y);
        }
        return *this;
    }
    bool operator<(const Point&rhs)const
    {
        Point p1 = Base(), p2 = rhs.Base();
        return p1.y * p2.x < p2.y * p1.x;
    }
    void input()
    {
        scanf("%lld %lld",&x,&y);
    }
}p[maxn],a[maxn];

Point operator * (Point a,ll b){return Point(a.x * b,a.y * b);}
Point operator + (Point a,Point b){return Point(a.x + b.x,a.y + b.y);}
Point operator - (Point a,Point b){return Point(a.x - b.x,a.y - b.y);}
Point operator / (Point a,ll b){return Point(a.x / b,a.y / b);}

map<Point,int>mp;
int res[maxn];

int main()
{
    int n,q;scanf("%d%d",&n,&q);
    for(int i = 1;i <= n;i++)
    {
        p[i].input();
    }
    
    for(int i = 1;i <= q;i++)
    {
        mp.clear();
        int ans = 0;
        a[i].input();
        for(int j = 1;j <= n;j++)
        {
            Point tmp;
            tmp = a[i] - p[j];
            mp[tmp]++;
        }
        
        map<Point,int>::iterator it;
        for(it = mp.begin();it != mp.end();it++)
        {
            Point tmp;
            tmp.x = -it->first.y;tmp.y = it->first.x;
            if(mp.count(tmp))
                ans += it->second * mp[tmp];
        }
        res[i] += ans / 2;
    }
    
    for(int i = 1;i <= n;i++)
    {
        mp.clear();
        for(int j = 1;j <= n;j++)
        {
            if(j == i)continue;
            mp[p[j] - p[i]]++;
        }
        for(int j = 1;j <= q;j++)
        {
            Point tmp = a[j] - p[i];
            tmp = Point(-tmp.y,tmp.x);
            if(mp.count(tmp))
                res[j] += mp[tmp];
        }
    }
    for(int i = 1;i <= q;i++)
    {
        printf("%d\n",res[i]);
    }
    
    return 0;
}