QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#380829#2434. Single Cut of Failure8BQube#WA 99ms13572kbC++202.3kb2024-04-07 13:07:392024-04-07 13:07:39

Judging History

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

  • [2024-04-07 13:07:39]
  • 评测
  • 测评结果:WA
  • 用时:99ms
  • 内存:13572kb
  • [2024-04-07 13:07:39]
  • 提交

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.0;
    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: 3916kb

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

score: 0
Accepted
time: 73ms
memory: 12376kb

Test #11:

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

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

score: 0
Accepted
time: 98ms
memory: 12208kb

Test #20:

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

Test #21:

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

Test #22:

score: -100
Wrong Answer
time: 93ms
memory: 13104kb