Gym - 102361A Angle Beats

发表于 | 阅读数

给出$n$个点，再给出$m$个询问，每次询问给出一个点 $x$，我们需要回答包括点 $x$ 的直角三角形有多少个

对于以$x$为顶点的直角三角形，可以暴力匹配，每个向量与他垂直的向量。

同理对于以$x$为其他点的直角三角形，可以暴力匹配$A-a,A-B$,搜搜有多少$A-B$满足。
我这里使用的 差不多可以过。

1
map<pair<int,int>,int>mp;

或者重载$map$

1
2
3
4
5
bool operator<(const Point& b)const 
{
    Point p1 = base(); Point p2 = b.base();
    return p1.x * p2.y < p1.y * p2.x;
}

直接把共线的向量放在一起

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
struct point
{
    int x, y;

    point operator-(const point &p) const { return (point){x - p.x, y - p.y}; };
    point operator+(const point &p) const { return (point){x + p.x, y + p.y}; };
    int operator^(const point &p) const { return x * p.y - y * p.x; };
    int operator*(const point &p) const { return x * p.x + y * p.y; };
    point operator*(const int &p) const { return (point){x * p, y * p}; };
    void set()
    {
        if (x == 0 && y == 0)
            return;
        if (x == 0)
        {
            y = 1;
            return;
        }
        if (y == 0)
        {
            x = 1;
            return;
        }
        if (x < 0 && y < 0)
            x = -x, y = -y;
        if (x < 0 && y > 0)
            x = -x, y = -y;
        int p = gcd(abs(x), abs(y));
        x /= p, y /= p;
    }

} p[N], a[N], tmp[N];
int n, q;
int ans[N];
map<pii, int> mp;
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &p[i].x, &p[i].y);
    for (int i = 1; i <= q; i++)
        scanf("%d%d", &a[i].x, &a[i].y);
    for (int i = 1; i <= q; i++)
    {
        mp.clear();
        for (int j = 1; j <= n; j++)
        {
            tmp[j] = p[j] - a[i];
            tmp[j].set();
            mp[mk(tmp[j].x, tmp[j].y)]++;
        }

        for (int j = 1; j <= n; j++)
        {
            swap(tmp[j].x, tmp[j].y);
            tmp[j].x *= -1;
            tmp[j].set();
            ans[i] += mp[mk(tmp[j].x, tmp[j].y)];
        }
        ans[i] /= 2;
    }

    for (int i = 1; i <= n; i++)
    {

        mp.clear();
        for (int j = 1; j <= n; j++)
            if (i != j)
            {
                tmp[j] = p[j] - p[i];
                tmp[j].set();

                mp[mk(tmp[j].x, tmp[j].y)]++;
            }

        for (int j = 1; j <= q; j++)
        {
            tmp[j] = a[j] - p[i];

            swap(tmp[j].x, tmp[j].y);
            tmp[j].x *= -1;
            tmp[j].set();
            ans[j] += mp[mk(tmp[j].x, tmp[j].y)];
        }
    }
    for (int i = 1; i <= q; i++)
    {
        printf("%d\n", ans[i]);
    }
}