QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#593813#8779. Square of TrianglesbettererWA 37ms4144kbC++209.0kb2024-09-27 16:11:252024-09-27 16:11:27

Judging History

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

  • [2024-09-27 16:11:27]
  • 评测
  • 测评结果:WA
  • 用时:37ms
  • 内存:4144kb
  • [2024-09-27 16:11:25]
  • 提交

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;
    }
#ifndef ONLINE_JUDGE
    void print() const {
        ::print(make_pair(x, y));
    }
#endif
};

struct line {
    point p1, p2;

    [[nodiscard]] bool separate(const point& q1, const point& q2) const {
        double t1 = (q1 - p1).unit() * (p2 - p1).unit(), t2 = (q2 - p1).unit() * (p2 - p1).unit();
        return abs(t1) > 1e-6 && abs(t2) > 1e-6 && t1 * t2 < 0;
    }

    [[nodiscard]] bool intersect(const line& l) const {
        return separate(l.p1, l.p2) && l.separate(p1, p2);
    }
};

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;
    }

    [[nodiscard]] bool contains(const point& p) const {
        for (int i = 0; i < ps.size(); ++i) {
            if ((ps[i] - p).unit() * (ps[(i + 1) % ps.size()] - p).unit() < 1e-6) return false;
        }
        // for (int i = 0; i < ps.size(); ++i) {
        //     de((ps[i] - p) * (ps[(i + 1) % ps.size()] - p));
        // }
        return true;
    }

    [[nodiscard]] bool intersect(const triangle& t) const {
        for (int i = 0; i < ps.size(); ++i) {
            for (int j = 0; j < t.ps.size(); ++j) {
                if (line{ps[i], ps[(i + 1) % ps.size()]}.intersect({t.ps[j], t.ps[(j + 1) % t.ps.size()]}))return true;
            }
        }
        return false;
    }
#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 + .01)) {
                                goto end;
                            }
                        }
                    }
                }
                for (auto& t2 : ts) {
                    if (t2.intersect(tri2)) {
                        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]).unit() * (vp[i] - sta.back()).unit() <= 1e-6) {
                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 - 1) > 1e-6) {
            // des("not same area");
            // de(ans, area);
            return false;
        }
        if (abs(c / (4 * sqrt(area)) - 1) > 1e-6) {
            return false;
        }
        de(*this);
        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 (T == 19 && j == 4999960)output = true;
            }
            if (output && T <= 20 - 4) {
                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] / 100., a[1] / 100., a[2] / 100.));
            } 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: 0
Wrong Answer
time: 37ms
memory: 4144kb

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:

0
0
1

result:

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