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
| #include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
using db = double;
const db eps = 1e-15, pi = acos(-1.0);
struct Frac
{
int a, b;
int gcd(int a, int b) { return !b ? a : gcd(b, a%b); }
int sgn(int x) { return (x>0 ? 1 : -1); }
Frac() : a(0), b(1) {}
Frac(int x) : a(x), b(1) {}
Frac(int x, int y) { a = x, b = y; norm(); }
bool operator < (const Frac f) const { return 1ll*a*f.b < 1ll*b*f.a; }
bool operator == (Frac f) { return 1ll*a*f.b == 1ll*b*f.a; }
void norm()
{
int g = gcd(abs(a), abs(b));
a = a/g*sgn(b);
if(!a) b = 1;
else if(!b) a = 1;
else b = abs(b/g);
}
};
int sgn(db x) { return (x<-eps ? -1 : x>eps); }
int n, q;
struct P
{
int x, y;
}p[N];
Frac seq[N][N];
void pre()
{
for(int x=1; x<=n; x++)
{
for(int i=1; i<=n; i++)
if(i<x) seq[x][i] = Frac(p[i].y-p[x].y, p[i].x-p[x].x);
else if(i>x) seq[x][i-1] = Frac(p[i].y-p[x].y, p[i].x-p[x].x);
sort(seq[x]+1, seq[x]+n);
}
}
void solve()
{
for(int i=1; i<=n; i++) cin >> p[i].x >> p[i].y;
pre();
while(q--)
{
cin >> p[0].x >> p[0].y;
for(int i=1; i<=n; i++) seq[0][i] = Frac(p[i].y-p[0].y, p[i].x-p[0].x);
sort(seq[0]+1, seq[0]+n+1);
int ans = 0, ans2 = 0;
for(int i=1; i<=n; i++)
{
Frac k(-p[0].x+p[i].x, p[0].y-p[i].y);
ans += upper_bound(seq[i]+1, seq[i]+n, k) - lower_bound(seq[i]+1, seq[i]+n, k);
ans2 += upper_bound(seq[0]+1, seq[0]+n+1, k) - lower_bound(seq[0]+1, seq[0]+n+1, k);
}
cout << ans + ans2/2 << '\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
while(cin >> n >> q) solve();
return 0;
}
|