QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#568420#2434. Single Cut of FailurePoetryAC ✓479ms70656kbC++232.2kb2024-09-16 16:25:152024-09-16 16:25:16

Judging History

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

  • [2024-09-16 16:25:16]
  • 评测
  • 测评结果:AC
  • 用时:479ms
  • 内存:70656kb
  • [2024-09-16 16:25:15]
  • 提交

answer

#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

using ld = long double;

int n, w, h;
struct Point {
    ld x;

    friend std::ostream &operator<<(std::ostream &os, Point k) {
        if (k.x < h) {
            return os << 0 << " " << k.x;
        } else if (k.x < h + w) {
            return os << k.x - h << " " << h;
        } else if (k.x < 2 * h + w) {
            return os << w << " " << h - (k.x - h - w);
        } else {
            return os << w - (k.x - 2 * h - w) << " " << 0;
        }
    }
} ;

struct Node {
    Point pos;
    int id;

    bool operator<(const Node &w) const {
        return pos.x < w.pos.x;
    }
} ;
std::vector<Node> a;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cout.precision(10);
    std::cout << std::fixed;

    std::cin >> n >> w >> h;
    for (int i = 0; i < n; ++i) {
        int x0, y0, x1, y1;
        std::cin >> x0 >> y0 >> x1 >> y1;

        auto getpos = [&](int x, int y) {
            if (x == 0) {
                return y;
            }
            if (y == h) {
                return h + x;
            }
            if (x == w) {
                return h + w + (h - y);
            }
            return 2 * h + w + (w - x);
        } ;

        Point A{(ld)getpos(x0, y0)}, B{(ld)getpos(x1, y1)};
        if (A.x > B.x) {
            std::swap(A, B);
        }

        a.push_back({A, i});
        a.push_back({B, i});
    }

    a.push_back((Node){(Point){2.0 * h + 2 * w}, n});
    sort(a.begin(), a.end());

    std::vector<bool> vis(n + 1);
    for (int l = 0, r = 0; r < n * 2; vis[a[l++].id] = 0) {
        while (r < n * 2 && !vis[a[r].id]) {
            vis[a[r].id] = 1;
            ++r;
        }
        if (r - l == n) {
            std::cout << 1 << "\n";
            std::cout << (Point){a[l].pos.x - 0.1} << " " <<(Point){a[r].pos.x - 0.1};
            return 0;
        }
    }    

    std::cout << 2 << "\n";
    std::cout << (Point){h - 0.1} << " " << (Point){2 * h + w - 0.1} << "\n";
    std::cout << (Point){0.1} << " " << (Point){h + w + 0.1} << "\n";

    return 0;
}

Details

Test #1:

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

Test #2:

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

Test #3:

score: 0
Accepted
time: 1ms
memory: 4056kb

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 0
Accepted
time: 87ms
memory: 20836kb

Test #10:

score: 0
Accepted
time: 94ms
memory: 19844kb

Test #11:

score: 0
Accepted
time: 104ms
memory: 20616kb

Test #12:

score: 0
Accepted
time: 111ms
memory: 21344kb

Test #13:

score: 0
Accepted
time: 111ms
memory: 20576kb

Test #14:

score: 0
Accepted
time: 109ms
memory: 20648kb

Test #15:

score: 0
Accepted
time: 109ms
memory: 21244kb

Test #16:

score: 0
Accepted
time: 99ms
memory: 20576kb

Test #17:

score: 0
Accepted
time: 109ms
memory: 20944kb

Test #18:

score: 0
Accepted
time: 94ms
memory: 21128kb

Test #19:

score: 0
Accepted
time: 112ms
memory: 21380kb

Test #20:

score: 0
Accepted
time: 110ms
memory: 19896kb

Test #21:

score: 0
Accepted
time: 111ms
memory: 19776kb

Test #22:

score: 0
Accepted
time: 92ms
memory: 20892kb

Test #23:

score: 0
Accepted
time: 112ms
memory: 19964kb

Test #24:

score: 0
Accepted
time: 455ms
memory: 69544kb

Test #25:

score: 0
Accepted
time: 459ms
memory: 69748kb

Test #26:

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

Test #27:

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

Test #28:

score: 0
Accepted
time: 1ms
memory: 3884kb

Test #29:

score: 0
Accepted
time: 2ms
memory: 3956kb

Test #30:

score: 0
Accepted
time: 13ms
memory: 5280kb

Test #31:

score: 0
Accepted
time: 390ms
memory: 69444kb

Test #32:

score: 0
Accepted
time: 479ms
memory: 69488kb

Test #33:

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

Test #34:

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

Test #35:

score: 0
Accepted
time: 1ms
memory: 3824kb

Test #36:

score: 0
Accepted
time: 4ms
memory: 4088kb

Test #37:

score: 0
Accepted
time: 12ms
memory: 5372kb

Test #38:

score: 0
Accepted
time: 78ms
memory: 19944kb

Test #39:

score: 0
Accepted
time: 464ms
memory: 70316kb

Test #40:

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

Test #41:

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

Test #42:

score: 0
Accepted
time: 1ms
memory: 4052kb

Test #43:

score: 0
Accepted
time: 3ms
memory: 4092kb

Test #44:

score: 0
Accepted
time: 35ms
memory: 13352kb

Test #45:

score: 0
Accepted
time: 302ms
memory: 69388kb

Test #46:

score: 0
Accepted
time: 440ms
memory: 70656kb

Test #47:

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

Test #48:

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

Test #49:

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

Test #50:

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

Test #51:

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

Test #52:

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

Test #53:

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

Test #54:

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

Test #55:

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

Test #56:

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

Test #57:

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

Test #58:

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

Test #59:

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

Test #60:

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

Test #61:

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

Test #62:

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

Test #63:

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

Test #64:

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

Test #65:

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

Test #66:

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

Test #67:

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

Test #68:

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

Test #69:

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

Test #70:

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

Test #71:

score: 0
Accepted
time: 34ms
memory: 12648kb

Test #72:

score: 0
Accepted
time: 31ms
memory: 13324kb

Test #73:

score: 0
Accepted
time: 34ms
memory: 12688kb

Test #74:

score: 0
Accepted
time: 35ms
memory: 12648kb

Test #75:

score: 0
Accepted
time: 34ms
memory: 13200kb

Test #76:

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