QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#661866#7803. H-Shaped Figuresucup-team1001WA 3ms3676kbC++237.0kb2024-10-20 18:36:472024-10-20 18:36:50

Judging History

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

  • [2024-10-20 18:36:50]
  • 评测
  • 测评结果：WA
  • 用时：3ms
  • 内存：3676kb
查看
  • [2024-10-20 18:36:47]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define irep(i, l, r) for(int i = l; i <= r; ++ i)
#define drep(i, r, l) for(int i = r; i >= l; -- i)
const int mod = 998244353;

typedef long long LD;

int sgn(LD x) {
    if (x > 0)return 1;
    if (x == 0)return 0;
    return -1;
}

struct frac {
    LD a, b;// a / sqrt(b)
    frac(LD aa = 0, LD bb = 1) {
        a = aa, b = bb;
    }

    bool operator==(const frac &A) const {
        if (sgn(a) != sgn(A.a))return false;
        __int128 AA = __int128(a) * a, BB = b, CC =  __int128(A.a) * A.a, DD = A.b;
        __int128 D = __gcd(AA, BB), E = __gcd(CC, DD);
        AA /= D, BB /= D, CC /= E, DD /= E;
        return make_pair(AA, BB) == make_pair(CC, DD);
    }

    bool operator<(const frac &A) const {
        return ((long double)(1.0)* a / sqrtl(b)) < ((long double)(1.0)* A.a / sqrtl(A.b));
    }

};


struct point {
    LD x, y;

    point(LD xx = 0, LD yy = 0) {
        x = xx, y = yy;
    }

    friend LD dot(const point &a, const point &b) {
        return a.x * b.x + a.y * b.y;
    }

    friend LD det(const point &a, const point &b) {
        return a.x * b.y - a.y * b.x;
    }

    bool operator==(const point &a) const {
        return a.x == x and a.y == y;
    }

    point operator-(const point &a) const {
        return {x - a.x, y - a.y};
    }
};

struct bit {
    int n;
    vector<int> t;

    bit(int m) {
        n = m;
        t.resize(n + 10);
    }

    int ask(int x) {
        int ans = 0;
        for (; x; x -= x & -x)
            ans += t[x];
        return ans;
    }

    void add(int x, int v) {
        for (; x <= n; x += (x & -x))
            t[x] += v;
    }
};

ll count_2d(int n, vector<array<int, 2>> a, vector<array<int, 2>> b) {
    bit T(n);
    vector<array<int, 3>> arr;
    for (auto [i, j]: a) {
        arr.push_back({i, 1, j});
    }
    for (auto [i, j]: b) {
        arr.push_back({i, 0, j});
    }
    sort(arr.begin(), arr.end());
    ll sum = 0;
    for (auto [I, tp, x]: arr) {
        if (tp == 0)sum += T.ask(x);
        else T.add(x, 1);
    }
    return sum;
}

void solve() {
    int n;
    point P, Q;
    cin >> P.x >> P.y >> Q.x >> Q.y;
    // swap(P, Q);
    cin >> n;
    vector<point> aa, bb, a, b;
    ll sum1 = 0, sum2 = 0;
    ll ans = 0;
    irep(i, 0, n - 1) {
        point L, R;
        cin >> L.x >> L.y >> R.x >> R.y;
//        cerr << det(L - P, R - P) << ' ' << dot(L - P, R - P) << ' ' << det(L - Q, R - Q) << endl;
        if (det(L - P, R - P) == 0 and dot(L - P, R - P) < 0 and det(L - Q, R - Q) != 0)
            aa.push_back(L), aa.push_back(R);
        if (det(L - Q, R - Q) == 0 and dot(L - Q, R - Q) < 0 and det(L - P, R - P) != 0)
            bb.push_back(L), bb.push_back(R);
    }
    ans = (1ll * aa.size() * bb.size()) / 4;

    for (auto A: aa) {
        if (det(A - Q, P - Q) > 0)
            a.push_back(A);
    }
    for (auto A: bb) {
        if (det(A - Q, P - Q) > 0)
            b.push_back(A);
    }
    vector<pair<frac, int>> cosA;
    vector<frac> cosALL;
    vector<array<int, 2>> TA, TB;
    for (auto p: a) {
        cosA.push_back({{dot(p - Q, P - Q), dot(p - Q, p - Q)}, 0});
        cosALL.emplace_back(dot(p - P, Q - P), dot(p - P, p - P));
        cosALL.emplace_back(dot(p - Q, P - Q), dot(p - Q, p - Q));
    }
    for (auto p: b) {
        cosA.push_back({{dot(p - Q, P - Q), dot(p - Q, p - Q)}, 1});
        cosALL.emplace_back(dot(p - P, Q - P), dot(p - P, p - P));
        cosALL.emplace_back(dot(p - Q, P - Q), dot(p - Q, p - Q));
    }

    sort(cosA.begin(), cosA.end());
    sort(cosALL.begin(), cosALL.end());
    reverse(cosA.begin(), cosA.end());
    cosALL.erase(unique(cosALL.begin(), cosALL.end()), cosALL.end());
    ll typeB = 0;
    for (auto [FR, tp]: cosA) {
//        cerr << FR.a << ' ' << FR.b << endl;
//        cerr << tp << ' ' << endl;
        if (tp)++typeB;
        else sum1 += typeB;
    }
    for (auto p: a) {
        frac t1 = {dot(p - P, Q - P), dot(p - P, p - P)},
                t2 = {dot(p - Q, P - Q), dot(p - Q, p - Q)};
        TA.push_back({int(lower_bound(cosALL.begin(), cosALL.end(), t1) - cosALL.begin()) + 1,
                      int(lower_bound(cosALL.begin(), cosALL.end(), t2) - cosALL.begin()) + 1});
    }
    for (auto p: b) {
        frac t1 = {dot(p - P, Q - P), dot(p - P, p - P)},
                t2 = {dot(p - Q, P - Q), dot(p - Q, p - Q)};
        TB.push_back({int(lower_bound(cosALL.begin(), cosALL.end(), t1) - cosALL.begin()) + 1,
                      int(lower_bound(cosALL.begin(), cosALL.end(), t2) - cosALL.begin()) + 1});
    }
    sum2 += count_2d(cosALL.size() + 3, TA, TB);
    cosA.clear(), cosALL.clear(), TA.clear(), TB.clear(), a.clear(), b.clear();

    //---------------------------------------------------------------------------------------------------------
    for (auto A: aa) {
        if (det(A - Q, P - Q) < 0)
            a.push_back(A);
    }
    for (auto A: bb) {
        if (det(A - Q, P - Q) < 0)
            b.push_back(A);
    }

    for (auto p: a) {
        cosA.push_back({{dot(p - Q, P - Q), dot(p - Q, p - Q)}, 0});
        cosALL.emplace_back(dot(p - P, Q - P), dot(p - P, p - P));
        cosALL.emplace_back(dot(p - Q, P - Q), dot(p - Q, p - Q));
    }
    for (auto p: b) {
        cosA.push_back({{dot(p - Q, P - Q), dot(p - Q, p - Q)}, 1});
        cosALL.emplace_back(dot(p - P, Q - P), dot(p - P, p - P));
        cosALL.emplace_back(dot(p - Q, P - Q), dot(p - Q, p - Q));
    }
    sort(cosA.begin(), cosA.end());
    reverse(cosA.begin(), cosA.end());
    sort(cosALL.begin(), cosALL.end());
    cosALL.erase(unique(cosALL.begin(), cosALL.end()), cosALL.end());
    typeB = 0;
    for (auto [FR, tp]: cosA) {
        if (tp)++typeB;
        else sum1 += typeB;
    }
    for (auto p: a) {
        frac t1 = {dot(p - P, Q - P), dot(p - P, p - P)},
                t2 = {dot(p - Q, P - Q), dot(p - Q, p - Q)};
        TA.push_back({int(lower_bound(cosALL.begin(), cosALL.end(), t1) - cosALL.begin()) + 1,
                      int(lower_bound(cosALL.begin(), cosALL.end(), t2) - cosALL.begin()) + 1});
    }
    for (auto p: b) {
        frac t1 = {dot(p - P, Q - P), dot(p - P, p - P)},
                t2 = {dot(p - Q, P - Q), dot(p - Q, p - Q)};
        TB.push_back({int(lower_bound(cosALL.begin(), cosALL.end(), t1) - cosALL.begin()) + 1,
                      int(lower_bound(cosALL.begin(), cosALL.end(), t2) - cosALL.begin()) + 1});
    }
    sum2 += count_2d(cosALL.size() + 3, TA, TB);
    cout << ans - sum1 + sum2 << '\n';
/*
4
0 0 4 0
8
0 0 2 1
-1 -1 2 2
3 3 5 -3
0 2 6 -1
2 -2 5 1
-1 1 3 -3
-1 0 2 0
-1 -1 2 2
0 0 4 0
2
-1 -1 2 2
3 1
5 -1
0 0 4 0
2
-1 -1 2 2
1 3
5 -1

0 0 4 0
2
-1 -1 2 2
1 1 7 -1

6
1
0
0
 */
}

int main() {
    frac A = {371884131150, 64678868005775570}, B = {2430385351992, 576903514247757000};

    ios::sync_with_stdio(false), cin.tie(0);
    int T = 1;
    cin >> T;
    while (T--)solve();
    return 0;
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3600kb

input:

1
0 0 4 0
8
0 0 2 1
-1 -1 2 2
3 3 5 -3
0 2 6 -1
2 -2 5 1
-1 1 3 -3
-1 0 2 0
-1 -1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

1
-1 0 0 1
2
1 1 0 -1
1 1 0 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

1
5 -5 7 2
2
-6 8 2 6
-7 -10 -5 10

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

10
-4 7 -10 -4
3
-3 3 -6 -9
-9 -3 -6 -9
-7 0 6 5
0 -5 -3 5
5
-7 -3 -5 -6
6 1 -3 4
1 -4 -4 7
-2 9 3 8
-4 -3 9 0
-9 -3 7 8
25
4 6 4 5
4 -6 -9 -6
-8 -8 10 -6
6 4 2 -7
2 -5 10 -4
-1 -9 -2 -1
-9 -10 6 6
-5 1 -5 -2
-1 -10 -6 1
9 -9 0 -4
-2 -4 -1 3
2 5 -10 1
9 7 6 4
-2 -5 -4 -3
-3 -5 5 -8
3 0 -6 1
6 3 7 2
...

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

10
-3 7 1 9
285
9 -5 0 8
-3 0 -1 8
-6 -7 8 -10
-3 -8 9 2
-4 9 -8 4
6 -10 9 -2
-10 -5 -2 10
7 -10 -2 2
7 7 10 -5
7 8 -7 -1
2 4 7 -4
3 -10 -9 8
7 -7 6 -3
10 10 -6 -2
-2 7 -8 3
0 -10 -9 5
7 3 -3 7
6 -8 -5 6
8 -8 7 7
-9 -1 10 7
-10 6 -4 -1
-6 -10 -6 0
9 6 2 -9
0 6 -1 -1
0 2 6 0
-9 -8 6 -2
10 7 -7 -5
2 5...

output:

1
0
9
0
0
0
0
0
0
0

result:

ok 10 numbers

Test #6:

score: -100
Wrong Answer
time: 3ms
memory: 3668kb

input:

10
-7 6 -3 1
1286
-9 -1 -2 -5
10 4 -2 0
0 6 -3 -10
-2 -9 2 -1
-10 2 -9 -2
1 -9 7 -4
-1 4 6 8
7 3 -9 9
5 2 -4 4
7 -9 -7 10
0 -2 0 6
3 -9 1 -10
-3 -4 -7 8
5 3 2 -1
5 2 -1 7
-9 -1 -6 -2
9 -6 10 0
8 -7 -7 -9
-10 8 -5 -9
-4 9 6 -9
-1 1 -3 -10
-7 -1 -6 3
5 4 -8 -1
-10 -10 5 0
-2 7 6 9
4 -3 -9 -2
10 -2 -7 ...

output:

9
238
0
0
162
0
15
0
17
10

result:

wrong answer 2nd numbers differ - expected: '237', found: '238'
English 繁體中文 简体中文

Server Time: 2024-12-01 00:22:16 | OpenSource Project