#include <bits/stdc++.h>
using namespace std;
#define REP(i, j, k) for (int i = (j); i < (k); i++)
#define RREP(i, j, k) for (int i = (j); i >= (k); i--)
template <class T>
inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005;
const int MAXN = 6005;
struct Point {
int x, y;
friend Point& operator+=(Point &l, const Point &r) {
l.x += r.x;
l.y += r.y;
return l;
}
friend Point& operator-=(Point &l, const Point &r) {
l.x -= r.x;
l.y -= r.y;
return l;
}
Point operator+(const Point &o) const {
Point res = *this;
return res += o;
}
Point operator-(const Point &o) const {
Point res = *this;
return res -= o;
}
friend istream& operator>>(istream &is, Point &o) {
return is >> o.x >> o.y;
}
friend ostream& operator<<(ostream &os, const Point &o) {
return os << "(" << o.x << ", " << o.y << ")";
}
};
ll cross(const Point &l, const Point &r) {
return (ll) l.x * r.y - (ll) l.y * r.x;
}
ll dot(const Point &l, const Point &r) {
return (ll) l.x * r.x + (ll) l.y * r.y;
}
int side(const Point &p) {
if (p.y > 0 || (p.y == 0 && p.x >= 0)) {
return 0;
}
return 1;
}
int n, m;
Point pt[MAXN];
vi grp[MAXN];
Point p[2];
int ord[2][MAXN];
int pos[MAXN][2];
vii rg[MAXN][2];
int q;
auto cmp(const Point &p) {
return [&] (int l, int r) {
Point lp = pt[l] - p, rp = pt[r] - p;
if (side(lp) != side(rp)) {
return side(lp) < side(rp);
}
return cross(lp, rp) > 0;
};
}
int main() {
#ifndef DEBUG
ios::sync_with_stdio(0), cin.tie(0);
#endif
cin >> n >> m;
REP (i, 0, n) {
int c; cin >> pt[i] >> c;
grp[c].pb(i);
}
cin >> p[0] >> p[1];
REP (z, 0, 2) {
iota(ord[z], ord[z] + n, 0);
sort(ord[z], ord[z] + n, cmp(p[z]));
REP (i, 0, n) {
ord[z][i + n] = ord[z][i];
}
}
REP (z, 0, 2) {
REP (i, 0, n) {
pos[ord[z][i]][z] = i;
}
}
REP (z, 0, 2) {
vi top, btm;
int r = 0;
REP (i, 0, n) {
Point cp = pt[ord[z][i]];
if (cross(cp - p[z], p[z ^ 1] - p[z]) > 0) {
mxto(r, i);
while (r + 1 < i + n && cross(cp - p[z], pt[ord[z][r + 1]] - p[z]) > 0) {
r++;
}
if (r < n) {
rg[ord[z][i]][z].pb({i, r});
} else {
rg[ord[z][i]][z].pb({i, n - 1});
rg[ord[z][i]][z].pb({0, r - n});
}
}
}
int l = 2 * n;
RREP (i, n - 1, 0) {
Point cp = pt[ord[z][i]];
if (cross(cp - p[z], p[z ^ 1] - p[z]) < 0) {
mnto(l, i + n);
while (l - 1 > i && cross(cp - p[z], pt[ord[z][l - 1]] - p[z]) < 0) {
l--;
}
if (l >= n) {
rg[ord[z][i]][z].pb({l - n, i});
} else {
rg[ord[z][i]][z].pb({l, n - 1});
rg[ord[z][i]][z].pb({0, i});
}
}
}
cerr << z << '\n';
REP (i, 0, n) {
cerr << ' ' << i << '\n';
for (auto [l, r] : rg[i][z]) {
cerr << " " << l << ' ' << r << '\n';
}
}
}
cin >> q;
while (q--) {
int f, g; cin >> f >> g;
int ans = 0;
for (int i : grp[f]) {
for (int j : grp[g]) {
bool bad = 0;
REP (z, 0, 2) {
bool gd = 0;
for (auto [l, r] : rg[i][z]) {
if (l <= pos[j][z] && pos[j][z] <= r) {
gd = 1;
break;
}
}
if (!gd) {
bad = 1;
break;
}
}
ans += !bad;
}
}
cout << ans << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
28 ms |
1024 KB |
Output is correct |
| 3 |
Correct |
37 ms |
1160 KB |
Output is correct |
| 4 |
Correct |
32 ms |
2052 KB |
Output is correct |
| 5 |
Correct |
23 ms |
2260 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1108 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1020 KB |
Output is correct |
| 9 |
Correct |
8 ms |
1024 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1772 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
28 ms |
1024 KB |
Output is correct |
| 3 |
Correct |
37 ms |
1160 KB |
Output is correct |
| 4 |
Correct |
32 ms |
2052 KB |
Output is correct |
| 5 |
Correct |
23 ms |
2260 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1108 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1020 KB |
Output is correct |
| 9 |
Correct |
8 ms |
1024 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1024 KB |
Output is correct |
| 11 |
Runtime error |
3 ms |
1772 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
