CCPC2019 秦皇岛 A Angle Beats

傻逼HDU

原题内存1G，贵题内存128M，真的nb

傻逼题，先对于一个点i，枚举所有点j，然后计算i和j构成的直线的斜率，记在i的map里（即对于每个点i，统计i作为线段一个端点的情况下，不同的斜率取值所对应的点的个数）

然后对于每个询问，分$A_i$是直角端点和非直角端点的情况讨论。

$A_i$是直角端点的情况下，枚举下n个点，算出来斜率的取值情况然后存起来。然后再枚举一个点，钦定这是第一条直角边，然后算出来另一条直角边的斜率，去刚刚存的map里反查有多少种情况，最后除个2（一种情况会被算两次）

$A_i$不是直角端点的情况下，枚举一个点，连起来构成一条直角边，然后算一下另一条直角边的斜率，然后去一开始预处理的数组里去查下能有多少种即可。（这个不需要除2，因为不会算重）

如何存斜率？别用浮点数，写个有理数类。如何记斜率不存在？分母写0，分子写1（分子不要写别的数，不方便统计）。如何记斜率为0？分子写1，分母写0。

另外为了统计方便，我们所存储的有理数均为最简分数，并且正负号全都在分子上（0和不存在除外，这时不需要考虑符号）

要做直接去CF交吧，HDU太傻逼了。

要用unordered_map并且自己写个hasher，map太慢了。

https://codeforces.com/gym/102361/problem/A

#include <assert.h>
#include <functional>
#include <iostream>
#include <map>
#include <unordered_map>
using int_t = long long int;

using std::cin;
using std::cout;
using std::endl;

int_t gcd(int_t a, int_t b) {
    a = std::abs(a);
    b = std::abs(b);
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

struct R {
    //有理数a/b
    int_t a = 0, b = 0;
    R simplify() const {
        int_t d = gcd(a, b);
        return R{a / d, b / d};
    }
    // R operator*(const R& rhs) const {
    //     if (b == 0 || rhs.b == 0)
    //         return R{1, 0};
    //     return R{a * rhs.a, b * rhs.b}.simplify();
    // }
    bool operator<(const R& rhs) const {
        return (long double)a / b < (long double)rhs.a / rhs.b;
    }
    bool operator==(const R& rhs) const { return a == rhs.a && b == rhs.b; }
    R(int_t a = 0, int_t b = 0) : a(a), b(b) {}
};

const auto my_hash = [](const R& x) -> size_t {
    return (((uint64_t)std::abs(x.a) << 31) | (uint64_t)std::abs(x.b)) %
           998244353;
};

struct my_hasher {
    size_t operator()(const R& x) const { return my_hash(x); }
};
//以某个点为一个端点的，斜率为R的点的个数
//无序点对
std::unordered_map<R, int, my_hasher> byS[2001];

struct P {
    int x, y;
} points[2001];
std::ostream& operator<<(std::ostream& os, const R& r) {
    os << "R{" << r.a << "," << r.b << "}";
    return os;
}
int n, q;
int main() {
    {
        (scanf("%d%d", &n, &q));
        // break;
        for (int i = 1; i <= n; i++) {
            auto& ref = points[i];
            scanf("%d%d", &ref.x, &ref.y);
            // byS[i].clear();
        }
        for (int i = 1; i <= n; i++) {
#ifdef DEBUG
            cout << "pnt " << i << " = " << points[i].x << " " << points[i].y
                 << endl;
#endif
            for (int j = 1; j <= n; j++) {
                if (i == j)
                    continue;
                int_t dy = points[j].y - points[i].y;
                int_t dx = points[j].x - points[i].x;
#ifdef DEBUG
                cout << "point " << i << " " << j << " dy = " << dy
                     << " dx = " << dx << endl;

#endif
                if (dx < 0) {
                    dy *= -1, dx *= -1;
                }
                int_t d = gcd(dy, dx);
                dy /= d, dx /= d;
                if (dx == 0)
                    dy = 1;
                else if (dy == 0)
                    dx = 1;
                byS[i][R{dy, dx}]++;
            }
        }

        while (q--) {
            int x, y;
            scanf("%d%d", &x, &y);
            int_t result = 0;
#ifdef DEBUG
            cout << "BEGIN " << x << " " << y << endl;
#endif
            //作为直角顶点 先预处理
            {
                int_t curr = 0;
                static std::unordered_map<R, int, my_hasher> byS;
                // for(int i=1;i<=n;i++) byS[i].clear();
                byS.clear();
                for (int i = 1; i <= n; i++) {
                    int_t dy = y - points[i].y;
                    int_t dx = x - points[i].x;
                    if (dx < 0) {
                        dy *= -1, dx *= -1;
                    }
                    int_t d = gcd(dy, dx);
                    dy /= d, dx /= d;
                    if (dx == 0)
                        dy = 1;
                    else if (dy == 0)
                        dx = 1;
                    byS[R{dy, dx}]++;
                }
#ifdef DEBUG
                for (const auto& kvp : byS) {
                    cout << kvp.first << " = " << kvp.second << endl;
                }
#endif

#ifdef DEBUG

                cout << "TYPE 2" << endl;
#endif
                //枚举一条直角边 然后根据斜率查另一条
                for (int i = 1; i <= n; i++) {
#ifdef DEBUG
                    cout << "FOR PNT " << i << endl;

#endif
                    int_t dy = y - points[i].y;
                    int_t dx = x - points[i].x;
                    dy *= -1;
                    if (dy < 0) {
                        dy *= -1, dx *= -1;
                    }
                    int_t d = gcd(dy, dx);
                    dy /= d, dx /= d;

                    R r0{dx, dy};
                    if (r0.b == 0) {
                        r0.a = 1;
                    } else if (r0.a == 0)
                        r0.b = 1;
                    if (byS.count(r0))
                        curr += byS[r0];
                }
#ifdef DEBUG
                cout << "type1 curr=" << curr << " div2 " << curr / 2 << endl;
#endif
                // assert(curr % 2 == 0);
                result += curr / 2;
            }
            //作为非直角顶点 枚举一个点，连上一条直角边，然后去查斜率
            {
                int_t curr = 0;
                for (int i = 1; i <= n; i++) {
                    int_t dy = y - points[i].y;
                    int_t dx = x - points[i].x;
                    dy *= -1;
                    if (dy < 0) {
                        dy *= -1, dx *= -1;
                    }
                    int_t d = gcd(dy, dx);
                    dx /= d, dy /= d;
                    R r0{dx, dy};
                    if (r0.b == 0)
                        r0.a = 1;
                    else if (r0.a == 0)
                        r0.b = 1;
                    if (byS[i].count(r0))
                        curr += byS[i][r0];
#ifdef DEBUG

                    cout << "type 2 at pnt " << i << " req r = " << r0
                         << " count " << byS[i][r0] << endl;
#endif
                }
                // assert(curr % 2 == 0);
#ifdef DEBUG
                cout << "type2 curr=" << curr << " div2 " << curr / 2 << endl;
#endif
                result += curr;
            }
            printf("%lld\n", result);
        }
    }
    return 0;
}