QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#593414#8779. Square of TrianglesbettererWA 2562ms16276kbC++207.8kb2024-09-27 13:54:452024-09-27 13:54:46

Judging History

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

  • [2024-09-27 13:54:46]
  • 评测
  • 测评结果:WA
  • 用时:2562ms
  • 内存:16276kb
  • [2024-09-27 13:54:45]
  • 提交

answer

#ifndef ONLINE_JUDGE
// #define ONLINE_JUDGE
#endif
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ull = unsigned long long;

#ifdef ONLINE_JUDGE
#define des(...)
#define de(...)
#else
#define des(x) cerr<<(x)<<endl
#endif

struct point {
    double x, y;

    bool operator<(const point& p) const {
        return x < p.x || (x == p.x && y < p.y);
    }

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

    point operator+(const point& p) const {
        return {x + p.x, y + p.y};
    }

    double operator*(const point& p) const {
        return x * p.y - y * p.x;
    }

    [[nodiscard]] point complex_mul(const point& p) const {
        return {x * p.x - y * p.y, x * p.y + y * p.x};
    }

    [[nodiscard]] point complex_div(const point& p) const {
        return {x * p.x + y * p.y, -x * p.y + y * p.x};
    }

    point operator*(const double v) const {
        return {x * v, y * v};
    }

    [[nodiscard]] double hypot() const {
        return ::hypot(x, y);
    }

    [[nodiscard]] point unit() const {
        return *this * (1 / hypot());
    }

    [[nodiscard]] double dot(const point& p) const {
        return x * p.x + y * p.y;
    }

    friend bool almost_line(const point& p, const point& q) {
        // return false;
        return p * q < 1e-6;
    }
#ifndef ONLINE_JUDGE
    void print() const {
        ::print(make_pair(x, y));
    }
#endif
};

struct triangle {
    vector<point> ps;


    static triangle from_edge(double x, double y, double z) {
        triangle ret;
        ret.ps.emplace_back(0, 0);
        ret.ps.emplace_back(sqrt(x), 0);
        double cos_angle = (x + y - z) / (2 * sqrt(x * y));
        ret.ps.emplace_back(sqrt(y) * cos_angle, sqrt(y) * sqrt(1 - cos_angle * cos_angle));
        return ret;
    }

    [[nodiscard]] double size() const {
        return abs((ps[1] - ps[0]) * (ps[2] - ps[0])) / 2;
    }
#ifndef ONLINE_JUDGE
    void print() const {
        ::print(ps);
    }
#endif
};

double area;

struct many_triangle {
    vector<triangle> ts;

    [[nodiscard]] vector<many_triangle> combine_with(const triangle& tri) const {
        vector<many_triangle> ret;
        for (auto& t : ts) {
            vector<int> perm(3);
            iota(perm.begin(), perm.end(), 0);
            do {
                auto vec1 = t.ps[perm[1]] - t.ps[perm[0]];
                auto vec2 = t.ps[perm[2]] - t.ps[perm[0]];
                auto angle = vec1 * vec2 > 0 ? vec1.complex_div(tri.ps[2]).unit() : vec1.unit();
                auto pos = t.ps[perm[0]];
                auto tri2 = tri;
                for (auto& p : tri2.ps)p = p.complex_mul(angle) + pos;
                // 剪枝,去掉过远点
                for (auto& p : tri2.ps) {
                    for (auto& t2 : ts) {
                        for (auto& p2 : t2.ps) {
                            if ((p - p2).hypot() > sqrt(area * 2) * (1 + 1e-6)) {
                                goto end;
                            }
                        }
                    }
                }
                {
                    many_triangle rt = *this;
                    rt.ts.push_back(tri2);
                    ret.push_back(rt);
                }
            end:;
            } while (ranges::next_permutation(perm).found);
        }
        return ret;
    }

    [[nodiscard]] bool check() const {
        vector<point> vp;
        for (auto& t : ts)for (auto& p : t.ps)vp.push_back(p);
        // 求凸包
        sort(vp.begin(), vp.end());
        sort(vp.begin() + 1, vp.end(), [&](const point& u, const point& v) {
            auto t = (u - vp[0]) * (v - vp[0]);
            if (t)return t > 0;
            return u < v;
        });
        vector<point> sta;
        sta.push_back(vp[0]);
        for (int i = 1; i < vp.size(); ++i) {
            while (sta.size() >= 2 && ((sta.back() - sta[sta.size() - 2]) * (vp[i] - sta.back()) <= 0 || almost_line(sta.back() - sta[sta.size() - 2], vp[i] - sta.back()))) {
                sta.pop_back();
            }
            sta.push_back(vp[i]);
        }
        // sta.push_back(vp[0]); //sta+1
        // if (sta.size() != 4) {
        //     // de(*this);
        //     // des("not 4 edges");
        //     return false;
        // }
        double s = 0, c = 0;
        for (int i = 1; i < sta.size(); ++i) {
            s += (sta[i - 1] - sta[0]) * (sta[i] - sta[0]) / 2;
        }
        vector<double> edges;
        for (int i = 0; i < sta.size(); ++i) {
            edges.push_back((sta[i] - sta[(i + 1) % sta.size()]).hypot());
            c += edges.back();
        }
        if (abs(s - area) / area > 1e-6) {
            // des("not same area");
            // de(ans, area);
            return false;
        }
        if (abs(c - 4 * sqrt(area)) > 1e-6) {
            return false;
        }
        // de(s, area, c, 4 * sqrt(area), sta);
        // ranges::sort(edges);
        // while (edges.front() < 1e-6) edges.erase(edges.begin());
        // de(edges.size(), edges);
        // if (edges.size() != 4) {
        //     des("not 4 edges");
        //     return false;
        // }
        // if (abs(edges.front() - edges.back()) > 1e-6) {
        //     des("not equal edges");
        //     // de(edges);
        //     return false;
        // }
        return true;
        if (abs((sta[0] - sta[1]).hypot() - (sta[1] - sta[2]).hypot()) > 1e-6) {
            des("not perpendicular");
            return false;
        }
        if (abs((sta[0] - sta[2]).dot((sta[1] - sta[3]))) > 1e-6) {
            // des("not square");
            return false;
        }
        // de(edges);
        return true;
    }
#ifndef ONLINE_JUDGE
    void print() const {
        ::print(ts);
    }
#endif
};

struct triangle_order {
    vector<int> v;
    int id;

    bool operator<(const triangle_order& t) const {
        return v < t.v;
    }
};

int T;
vector<int> a(3);

signed main() {
    bool output = false;
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> T;
    while (T--) {
        area = 0;
        vector<vector<triangle>> vvt;
        vector<triangle_order> vto;
        for (int i = 0; i < 4; ++i) {
            for (auto& j : a) {
                cin >> j;
                // if (j == 1148639)output = true;
            }
            if (output && T <= 16) {
                for (auto& j : a)cout << j << ' ';
                continue;
            }
            vvt.emplace_back();
            ranges::sort(a);
            if (i)vto.push_back({a, i});
            do {
                vvt.back().push_back(triangle::from_edge(a[0], a[1], a[2]));
            } while (ranges::next_permutation(a).found);
            area += vvt.back().back().size();
        }
        if (output) {
            cout << endl;
            continue;
        }
        for (int i = 0; i < 4; ++i) {
            de(i, vvt[i].size(), vvt[i]);
        }
        // exit(0);
        sort(vto.begin(), vto.end());
        do {
            vector<many_triangle> vmt, vmt2;
            vmt.push_back({{vvt[0][0]}});
            for (int i = 1; i < 4; ++i) {
                for (auto& mt : vmt) {
                    for (auto& t : vvt[vto[i - 1].id]) {
                        auto res = mt.combine_with(t);
                        vmt2.insert(vmt2.end(), res.begin(), res.end());
                    }
                }
                vmt = move(vmt2);
            }
            for (auto& mt : vmt) {
                if (mt.check()) {
                    cout << 1 << endl;
                    goto end;
                }
            }
        } while (next_permutation(vto.begin(), vto.end()));
        // de(vmt);
        cout << 0 << endl;
    end:;
        // exit(0);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 87ms
memory: 7756kb

input:

3
1 1 2
2 1 1
2 1 1
1 2 1
1 1 1
1 1 1
1 1 1
1 1 1
5 125 130
125 20 145
45 130 145
145 145 80

output:

1
0
1

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 534ms
memory: 9384kb

input:

20
1998001 7984010 9982009
1998001 7984010 1994005
7984010 9978013 9982009
9978013 1994005 7984010
9958045 7968034 9962037
7968034 1994005 9962037
9958045 1990013 7968034
1994005 1990013 7968034
7952074 9938097 1986025
7952074 9942085 1990013
7952074 9942085 9938097
1986025 7952074 1990013
7936130 9...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

result:

ok 20 lines

Test #3:

score: 0
Accepted
time: 1197ms
memory: 13600kb

input:

20
1148639 3581051 1216206
9999916 7026968 270268
6013463 6013463 6756700
6013463 6013463 6756700
2608850 8630930 9445800
9862940 6448880 6939290
8631650 3682160 5184310
7504700 6652150 1917140
2359505 3170711 2299108
4027811 6760781 2960240
4679918 6106006 3178400
8153446 7975057 5222088
8849500 88...

output:

0
0
0
1
1
1
1
0
1
1
1
1
1
0
0
0
0
1
1
1

result:

ok 20 lines

Test #4:

score: 0
Accepted
time: 2562ms
memory: 16276kb

input:

20
7300000 8100000 10000000
8100000 7300000 1000000
1000000 7300000 2900000
2900000 10000000 7300000
61728 8950560 9999936
7901184 4012320 4999968
8950560 3950592 4999968
4012320 123456 4999968
4494200 9932182 9932182
8381683 112355 9932182
5505395 9460291 9932182
9999595 4494200 9190639
5994936 671...

output:

1
1
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
1
0
0

result:

ok 20 lines

Test #5:

score: 0
Accepted
time: 1836ms
memory: 13216kb

input:

20
10000000 5078125 3828125
78125 5000000 5078125
1250000 10000000 6250000
5000000 6250000 1250000
7079600 5663680 1415920
7079600 796455 9999935
5663680 9999935 5752175
5663680 88495 5752175
4410468 1135368 9999972
5676840 4541472 5676840
4541472 5676840 5676840
8078580 742356 6288192
8345560 44707...

output:

1
1
0
0
0
1
1
1
1
1
1
0
0
1
0
1
0
1
0
0

result:

ok 20 lines

Test #6:

score: 0
Accepted
time: 1809ms
memory: 12812kb

input:

20
10000000 5078125 3828125
2031250 78125 1953125
703125 5078125 2031250
5000000 10000000 5000000
5000000 10000000 5000000
5000000 2890625 390625
6250000 1250000 10000000
1250000 2890625 3515625
6711400 9999986 3288586
4899322 4295296 604026
6979856 9999986 4899322
6711400 6979856 268456
9767552 645...

output:

1
1
1
0
1
1
0
1
1
0
1
1
0
0
1
0
0
1
0
0

result:

ok 20 lines

Test #7:

score: -100
Wrong Answer
time: 2236ms
memory: 15732kb

input:

20
3063559 8439238 9999919
3063559 9999919 3005756
8381435 9999919 8439238
8381435 3005756 9999919
6923007 4319483 4852022
2130156 4319483 769223
9999899 3076892 6923007
6923007 2899379 4852022
3271584 4999968 493824
6049344 61728 5246880
4999968 4999968 9999936
5246880 3271584 3950592
7398784 99999...

output:

1
1
1
1
0
1
0
0
1
0
0
0
0
1
0
0
1
1
0
0

result:

wrong answer 17th lines differ - expected: '0', found: '1'