QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#129799#4538. Bowlingbatrr#AC ✓402ms21420kbC++174.4kb2023-07-23 00:28:002023-07-23 00:28:04

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-23 00:28:04]
  • 评测
  • 测评结果:AC
  • 用时:402ms
  • 内存:21420kb
  • [2023-07-23 00:28:00]
  • 提交

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