QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#216818#2434. Single Cut of FailureSwarthmore#WA 830ms86484kbC++146.8kb2023-10-16 01:17:302023-10-16 01:17:31

Judging History

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

  • [2023-10-16 01:17:31]
  • 评测
  • 测评结果:WA
  • 用时:830ms
  • 内存:86484kb
  • [2023-10-16 01:17:30]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Point{
    ll x,y;
    Point (ll x_ = 0,ll y_ = 0) : x(x_), y(y_) {}
};

struct Seg{
    Point u,v;
};

struct Invl{
    ll l,r;
};

const int maxn = 1000005;
const ll inf = 1234567890;

Seg s[maxn],s2[maxn];

Point rotate90(Point p, ll h){
    return Point(h-p.y,p.x);
}

Point rotate90_inv(Point p, ll h){ // original h
    return Point(p.y,h-p.x);
}

inline int onSide(Point p,int w,int h){
    if (p.y == 0) return 0;
    if (p.x == w) return 1;
    if (p.y == h) return 2;
    if (p.x == 0) return 3;
    assert(false);
}

Point inversions(ll x_lower, ll x_upper, ll y_lower, ll y_upper, vector<Invl> inv){
    int n = inv.size();
    assert(x_lower < x_upper);
    assert(y_lower < y_upper);
    if (n == 0){
        return {x_lower + 1, y_lower + 1};
    }
    sort(inv.begin(), inv.end(), [](const Invl & a,const Invl & b){
        return a.l < b.l;
    });
    vector<ll> pre_min(n+1), suf_max(n+1);
    pre_min[0] = inf;
    for (int i = 1;i <= n;i++){
        pre_min[i] = min(pre_min[i-1], inv[i-1].r);
    }
    suf_max[n] = -inf;
    for (int i = n;i >= 1;i--){
        suf_max[i-1] = max(suf_max[i], inv[i-1].r);
    }
    inv.push_back({inf, inf});
    for (int i = 0;i <= n;i++){
        ll x_range_lower;
        if (i != 0) x_range_lower = max(x_lower+1, inv[i-1].l+1);
        else x_range_lower = x_lower + 1;
        ll x_range_upper = min(x_upper-1, inv[i].l-1);
        if (x_range_lower > x_range_lower) continue;
        // Consider x in this range;
        ll y_range_lower = max(suf_max[i] + 1, y_lower + 1);
        ll y_range_upper = min(pre_min[i] - 1, y_upper - 1);
        if (y_range_lower <= y_range_upper){
            return {x_range_lower, y_range_lower};
        }
    }
    return {-1,-1};
};

ostream& operator<<(ostream & os, Point p){
    os << (p.x / 2);
    if (p.x % 2 == 1) os << ".5";
    os << " ";
    os << (p.y / 2);
    if (p.y % 2 == 1) os << ".5";
    return os;
}

int main(){
    int n;
    cin >> n;
    ll w,h;
    cin >> w >> h;
    w <<= 1;
    h <<= 1;
    for (int i = 1;i <= n;i++){
        cin >> s[i].u.x >> s[i].u.y >> s[i].v.x >> s[i].v.y;
        s[i].u.x <<= 1;
        s[i].u.y <<= 1;
        s[i].v.x <<= 1;
        s[i].v.y <<= 1;
    }
    // Check "horizontal 1 way"
    for (int i = 1;i <= n;i++){
        s2[i] = s[i];
    }
    for (int i = 0;i < 2;i++){
        ll x_upper = w;
        ll x_lower = 0;
        ll y_upper = w;
        ll y_lower = 0;
        vector<Invl> inv;
        for (int j = 1;j <= n;j++){
            Point u = s2[j].u;
            Point v = s2[j].v;
            int u_side = onSide(u, w, h);
            int v_side = onSide(v, w, h);
            if (u_side % 2 == 1 && v_side % 2 == 1) continue;
            if (u_side % 2 == 0 && v_side % 2 == 0){
                if (u_side < v_side) swap(u,v);
                inv.push_back((Invl){u.x, v.x});
            }
            else{
                if (u_side % 2 == 0){
                    swap(u,v);
                    swap(u_side,v_side);
                }
                if (u_side == 1 && v_side == 0){
                    y_lower = max(y_lower, v.x);
                }
                if (u_side == 1 && v_side == 2){
                    x_lower = max(x_lower, v.x);
                }
                if (u_side == 3 && v_side == 0){
                    y_upper = min(y_upper, v.x);
                }
                if (u_side == 3 && v_side == 2){
                    x_upper = min(x_upper, v.x);
                }
            }
        }
    //    printf("x in [%lld, %lld] y in [%lld,%lld]\n",x_lower,x_upper,y_lower,y_upper);
        if (x_lower < x_upper && y_lower < y_upper){
          // Find restriction on lower - upper edges
          auto [lower,upper] = inversions(x_lower, x_upper, y_lower, y_upper, inv);
          if (lower > 0){
              cout << "1\n";
              Point x = Point(lower, h);
              Point y = Point(upper, 0);
              if (i == 1){
                   x = rotate90_inv(x, w);
                   y = rotate90_inv(y, w);
              }
              cout << x << " " << y << endl;

              exit(0);
          }
        }

        for (int j = 1;j <= n;j++){
            s2[j].u = rotate90(s2[j].u, h);
            s2[j].v = rotate90(s2[j].v, h);
        }
        swap(w,h);
    }
    for (int i = 1;i <= n;i++){
        s2[i] = s[i];
    }
    for (int i = 0;i < 4;i++){
        ll x_lower = 0;
        ll x_upper = w;
        ll y_lower = 0;
        ll y_upper = h;
        vector<Invl> inv;
        bool tf = true;
        for (int j = 1;j <= n;j++){
            Point u = s2[j].u;
            Point v = s2[j].v;
            int u_side = onSide(u, w, h);
            int v_side = onSide(v, w, h);
            if (u_side % 2 != v_side % 2){
                if (u_side % 2 == 0){
                    swap(u,v);
                    swap(u_side, v_side);
                }
                if (u_side == 1 && v_side == 2){
                    tf = false;
                    break;
                }
                if (u_side == 1 && v_side == 0){
                   x_lower = max(x_lower, v.x);
                }
                if (u_side == 3 && v_side == 0){
                    inv.push_back({v.x, u.y});
                }
                if (u_side == 3 && v_side == 2){
                    y_lower = max(y_lower, u.y);
                }
            }
            else if (u_side % 2 == 0){
                if (u_side != 0){
                    swap(u,v);
                    swap(u_side, v_side);
                }
                x_lower = max(x_lower, u.x);
            }
            else{
                if (u_side != 3){
                    swap(u,v);
                    swap(u_side, v_side);
                }
                y_lower = max(y_lower, u.y);
            }
        }
        if (tf && x_lower < x_upper && y_lower < y_upper){
          // Find restriction on lower - upper edges
          auto [lower,upper] = inversions(x_lower, x_upper, y_lower, y_upper, inv);
          if (lower > 0){
              cout << "1\n";
              Point x = Point(lower, 0);
              Point y = Point(0, upper);
              for (int j = 1;j <= i;j++){
                  x = rotate90_inv(x, w);
                  y = rotate90_inv(y, w);
                  swap(h,w);
              }
              cout << x << " " << y << endl;
              exit(0);
          }
        }
        for (int j = 1;j <= n;j++){
            s2[j].u = rotate90(s2[j].u, h);
            s2[j].v = rotate90(s2[j].v, h);
        }
        swap(w,h);
    }
    cout << 2 << endl;
    cout << Point(1, 0) << " " << Point(w-1,h) << endl;
    cout << Point(w-1, 0) << " " << Point(1,h) << endl;
}

Details

Test #1:

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

Test #2:

score: 0
Accepted
time: 6ms
memory: 65924kb

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 0
Accepted
time: 145ms
memory: 65996kb

Test #10:

score: 0
Accepted
time: 154ms
memory: 83068kb

Test #11:

score: 0
Accepted
time: 204ms
memory: 75072kb

Test #12:

score: 0
Accepted
time: 198ms
memory: 65992kb

Test #13:

score: 0
Accepted
time: 198ms
memory: 65900kb

Test #14:

score: 0
Accepted
time: 204ms
memory: 65964kb

Test #15:

score: 0
Accepted
time: 200ms
memory: 65924kb

Test #16:

score: 0
Accepted
time: 202ms
memory: 73960kb

Test #17:

score: 0
Accepted
time: 197ms
memory: 65960kb

Test #18:

score: 0
Accepted
time: 169ms
memory: 65996kb

Test #19:

score: 0
Accepted
time: 197ms
memory: 66028kb

Test #20:

score: 0
Accepted
time: 181ms
memory: 65968kb

Test #21:

score: 0
Accepted
time: 207ms
memory: 65964kb

Test #22:

score: 0
Accepted
time: 180ms
memory: 65992kb

Test #23:

score: 0
Accepted
time: 191ms
memory: 65904kb

Test #24:

score: -100
Wrong Answer
time: 830ms
memory: 86484kb