QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#129799 | #4538. Bowling | batrr# | AC ✓ | 402ms | 21420kb | C++17 | 4.4kb | 2023-07-23 00:28:00 | 2023-07-23 00:28:04 |
Judging History
answer
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
const int N = 300500, inf = 1e9, mod = 998244353;
const ll INF = 1e18;
mt19937 rnd(228);
int n;
const int maxN = 1e5 + 10;
struct pt{
ll x, y;
pt() {
x = y = 0;
}
pt(ll _x, ll _y) {
x = _x;
y = _y;
}
};
pt poly[maxN];
pt query[maxN];
bool ccw(pt a, pt b, pt c) {
return (b.x - a.x) * (c.y - a.y) > (b.y - a.y) * (c.x - a.x);
}
int best_R = 1;
int best_L = 1;
pt cur;
void upd(int id) {
if (ccw(cur, poly[id], poly[best_L])) best_L = id;
if (ccw(cur, poly[best_R], poly[id])) best_R = id;
}
ll sgn(ll val) {
if (val > 0) return 1;
else return -1;
}
void calc() {
best_R = 1;
best_L = 1;
upd(n);
ll A = 2 * cur.y - (poly[1].y + poly[n].y);
ll B = poly[1].x + poly[n].x - 2 * cur.x;
ll C = -A * cur.x - B * cur.y;
int R = n;
int L = 1;
ll his_val = sgn(1);
while (R - L > 1) {
int mid = (L + R) / 2;
if (sgn(poly[mid].x * A + poly[mid].y * B + C) == his_val) {
L = mid;
}
else {
R = mid;
}
}
vector<pair<int,int>> S = {{1, L}, {R, n}};
for (auto& [le, ri] : S) {
for (bool flag : {false, true}) {
int lo = le - 1;
int hi = ri;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if ((ccw(cur, poly[mid], poly[mid + 1]) ^ flag)) {
lo = mid;
}
else {
hi = mid;
}
}
assert(le <= hi && hi <= ri);
upd(hi);
}
}
}
bool operator == (const pt& a, const pt& b) {
return (a.x == b.x && a.y == b.y);
}
int tp(pt a) {
if (a.y < 0 || (a.y == 0 && a.x > 0)) return -1;
return 1;
}
pt T(0, 0);
bool cmp(pt a, pt b) {
if (tp(a) != tp(b)) {
return tp(a) < tp(b);
}
return ccw(T, b, a);
}
void norm(pt& t) {
int D = __gcd(abs(t.x), abs(t.y));
t.x /= D;
t.y /= D;
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> poly[i].x >> poly[i].y;
}
int m;
cin >> m;
vector<pair<pt,pt>> ADD;
vector<pt> evs;
for (int i = 1; i <= m; i++) {
cin >> query[i].x >> query[i].y;
cur.x = query[i].x;
cur.y = query[i].y;
calc();
assert(ccw(cur, poly[best_L], poly[best_R]));
pt difL(cur.x - poly[best_R].x, cur.y - poly[best_R].y);
pt difR(cur.x - poly[best_L].x, cur.y - poly[best_L].y);
norm(difL);
norm(difR);
evs.emplace_back(difL);
evs.emplace_back(difR);
ADD.push_back(make_pair(difL, difR));
}
int q;
cin >> q;
vector<pt> ASK(q);
for (int i = 0; i < q; i++) {
cin >> ASK[i].x >> ASK[i].y;
norm(ASK[i]);
evs.emplace_back(ASK[i]);
}
sort(evs.begin(), evs.end(), cmp);
evs.erase(unique(evs.begin(), evs.end()), evs.end());
// cout << " GGGG " << endl;
// for (auto& it : evs) {
// cout << it.x << " " << it.y << endl;
// }
// cout << " CHECK " << endl;
vector<int> tot(evs.size() + 1);
for (int i = 0; i < ADD.size(); i++) {
int L = lower_bound(evs.begin(), evs.end(), ADD[i].first, cmp) - evs.begin();
int R = lower_bound(evs.begin(), evs.end(), ADD[i].second, cmp) - evs.begin();
// cout << L << " " << R << " ?? " << endl;
assert(L != R && max(L, R) < evs.size());
if (L <= R) {
tot[L]++;
tot[R + 1]--;
}
else {
tot[0]++;
tot[R + 1]--;
tot[L]++;
}
}
for (int i = 1; i < tot.size(); i++) {
tot[i] += tot[i - 1];
}
for (int i = 0; i < q; i++) {
int pos = lower_bound(evs.begin(), evs.end(), ASK[i], cmp) - evs.begin();
// cout << pos << " ? " << endl;
cout << tot[pos] << '\n';
}
}
int main() {
#ifdef DEBUG
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
int t = 100000;
cin >> t;
for (int i = 1; i <= t; i++) {
// cout << "Case #" << i << endl;
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 402ms
memory: 21420kb
input:
56 4 0 0 2 0 2 2 0 2 5 1 4 3 1 4 2 5 1 3 3 3 0 1 1 0 1 1 3 -9 -5 -1 -2 -3 0 100 7 -49 -69 81 20 77 -3 47 2 45 76 82 65 -70 85 3 82 62 23 -32 83 -66 58 -58 52 -90 4 -33 5 -97 -8 62 89 -64 31 -88 19 87 -62 -34 7 55 12 2 16 77 93 -7 13 15 -21 62 41 72 55 13 -70 45 -5 49 51 93 73 -21 3 22 -49 22 -83 -80...
output:
1 3 3 1 4 4 5 1 2 1 4 3 0 4 2 2 2 1 1 1 4 3 0 4 2 4 5 2 1 3 2 1 1 3 2 4 3 2 2 0 2 1 2 2 2 1 2 0 1 1 1 1 2 1 0 3 3 4 3 0 1 4 3 0 1 0 3 2 1 1 1 2 2 4 4 4 5 1 1 3 4 1 0 1 3 2 1 1 4 3 1 3 4 4 1 5 1 3 1 1 2 1 4 7 5 7 6 4 3 6 5 2 2 4 6 4 7 7 8 7 2 2 5 2 5 2 1 7 8 2 0 1 4 3 7 2 7 5 3 5 1 3 2 2 5 4 3 5 6 2 ...
result:
ok 194003 lines