QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#380907#2434. Single Cut of Failure8BQube#AC ✓412ms38648kbC++202.3kb2024-04-07 14:50:172024-04-07 14:50:18

Judging History

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

  • [2024-04-07 14:50:18]
  • 评测
  • 测评结果:AC
  • 用时:412ms
  • 内存:38648kb
  • [2024-04-07 14:50:17]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())

int n, w, h;

ll hs(ll x, ll y) {
    if (y == 0)
        return x;
    if (x == w)
        return w + y;
    if (y == h)
        return w + h + (w - x);
    assert(x == 0);
    return w + h + w + (h - y);
}
const double eps = 1e-9;
pair<double, double> rhs(double t) {
    if (t >= w + h + w + h)
        t -= w + h + w + h;
    if (t <= w)
        return {t, 0};
    t -= w;
    if (t <= h)
        return {w, t};
    t -= h;
    if (t <= w)
        return {w - t, h};
    t -= w;
    assert(t <= h);
    return {0, h - t};
}

void output(double t) {
    t += 0.1;
    auto [x, y] = rhs(t);
    cout << fixed << setprecision(1) << x << " " << y;
}

const int N = 1e6 + 6;
int cnt[N], cc = 0;
vector<pll> v;

void case1(int l, int r) { // [l, r]
    assert(r + 1 < SZ(v));
    double a, b;
    if (l == 0)
        a = 0.1;
    else
        a = (v[l - 1].X + v[l].X) / 2.0;
    b = (v[r].X + v[r + 1].X) / 2.0;
    auto [ax, ay] = rhs(a);
    auto [bx, by] = rhs(b);
    auto both = [&](double x, double y, double c) {
        return abs(x - c) < eps && abs(y - c) < eps;   
    };

    if (both(ay, by, 0))
        b = w;
    else if (both(ax, bx, w))
        b = w + h;
    else if (both(ay, by, h))
        b = w + h + w;
    else if (both(ax, bx, 0))
        b = 0;
    
    cout << 1 << "\n";
    output(a);
    cout << " ";
    output(b);
    cout << "\n";
    exit(0);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> w >> h;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            int x, y;
            cin >> x >> y;
            v.pb({hs(x, y), i});
        }
    }
    sort(ALL(v));
    assert(SZ(v) == 2 * n);
    for (int i = 0; i < SZ(v); i++) {
        cnt[v[i].Y]++;
        if (cnt[v[i].Y] == 1)
            cc++;
        if (i - n >= 0) {
            cnt[v[i - n].Y]--;
            if (cnt[v[i - n].Y] == 0)
                --cc;
        }
        if (cc == n)
            case1(i - n + 1, i);
    }
    cout << 2 << "\n";
    output(0); cout << " "; output(w + h); cout << "\n";
    output(w); cout << " "; output(w + h + w); cout << "\n";
}

Details

Test #1:

score: 100
Accepted
time: 1ms
memory: 3844kb

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 0
Accepted
time: 91ms
memory: 12172kb

Test #10:

score: 0
Accepted
time: 81ms
memory: 12096kb

Test #11:

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

Test #12:

score: 0
Accepted
time: 95ms
memory: 12084kb

Test #13:

score: 0
Accepted
time: 86ms
memory: 12172kb

Test #14:

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

Test #15:

score: 0
Accepted
time: 93ms
memory: 12184kb

Test #16:

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

Test #17:

score: 0
Accepted
time: 89ms
memory: 12228kb

Test #18:

score: 0
Accepted
time: 85ms
memory: 12176kb

Test #19:

score: 0
Accepted
time: 91ms
memory: 12060kb

Test #20:

score: 0
Accepted
time: 89ms
memory: 12116kb

Test #21:

score: 0
Accepted
time: 95ms
memory: 12260kb

Test #22:

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

Test #23:

score: 0
Accepted
time: 96ms
memory: 12116kb

Test #24:

score: 0
Accepted
time: 404ms
memory: 38648kb

Test #25:

score: 0
Accepted
time: 412ms
memory: 38648kb

Test #26:

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

Test #27:

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

Test #28:

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

Test #29:

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

Test #30:

score: 0
Accepted
time: 7ms
memory: 4376kb

Test #31:

score: 0
Accepted
time: 343ms
memory: 36100kb

Test #32:

score: 0
Accepted
time: 403ms
memory: 38456kb

Test #33:

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

Test #34:

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

Test #35:

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

Test #36:

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

Test #37:

score: 0
Accepted
time: 8ms
memory: 4268kb

Test #38:

score: 0
Accepted
time: 62ms
memory: 11508kb

Test #39:

score: 0
Accepted
time: 380ms
memory: 38500kb

Test #40:

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

Test #41:

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

Test #42:

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

Test #43:

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

Test #44:

score: 0
Accepted
time: 30ms
memory: 7268kb

Test #45:

score: 0
Accepted
time: 259ms
memory: 36216kb

Test #46:

score: 0
Accepted
time: 376ms
memory: 38568kb

Test #47:

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

Test #48:

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

Test #49:

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

Test #50:

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

Test #51:

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

Test #52:

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

Test #53:

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

Test #54:

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

Test #55:

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

Test #56:

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

Test #57:

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

Test #58:

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

Test #59:

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

Test #60:

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

Test #61:

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

Test #62:

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

Test #63:

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

Test #64:

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

Test #65:

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

Test #66:

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

Test #67:

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

Test #68:

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

Test #69:

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

Test #70:

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

Test #71:

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

Test #72:

score: 0
Accepted
time: 14ms
memory: 7252kb

Test #73:

score: 0
Accepted
time: 24ms
memory: 7332kb

Test #74:

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

Test #75:

score: 0
Accepted
time: 22ms
memory: 7352kb

Test #76:

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