QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#216820#2434. Single Cut of FailureSwarthmore#AC ✓890ms86808kbC++146.8kb2023-10-16 01:22:472023-10-16 01:22:48

Judging History

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

  • [2023-10-16 01:22:48]
  • 评测
  • 测评结果:AC
  • 用时:890ms
  • 内存:86808kb
  • [2023-10-16 01:22:47]
  • 提交

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

详细

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 0
Accepted
time: 142ms
memory: 66008kb

Test #10:

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

Test #11:

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

Test #12:

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

Test #13:

score: 0
Accepted
time: 205ms
memory: 66036kb

Test #14:

score: 0
Accepted
time: 208ms
memory: 66104kb

Test #15:

score: 0
Accepted
time: 213ms
memory: 66292kb

Test #16:

score: 0
Accepted
time: 208ms
memory: 74864kb

Test #17:

score: 0
Accepted
time: 212ms
memory: 66068kb

Test #18:

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

Test #19:

score: 0
Accepted
time: 212ms
memory: 66092kb

Test #20:

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

Test #21:

score: 0
Accepted
time: 201ms
memory: 66260kb

Test #22:

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

Test #23:

score: 0
Accepted
time: 203ms
memory: 66296kb

Test #24:

score: 0
Accepted
time: 885ms
memory: 85312kb

Test #25:

score: 0
Accepted
time: 890ms
memory: 86808kb

Test #26:

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

Test #27:

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

Test #28:

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

Test #29:

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

Test #30:

score: 0
Accepted
time: 19ms
memory: 66224kb

Test #31:

score: 0
Accepted
time: 713ms
memory: 72416kb

Test #32:

score: 0
Accepted
time: 801ms
memory: 72476kb

Test #33:

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

Test #34:

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

Test #35:

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

Test #36:

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

Test #37:

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

Test #38:

score: 0
Accepted
time: 149ms
memory: 71948kb

Test #39:

score: 0
Accepted
time: 781ms
memory: 73020kb

Test #40:

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

Test #41:

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

Test #42:

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

Test #43:

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

Test #44:

score: 0
Accepted
time: 65ms
memory: 66156kb

Test #45:

score: 0
Accepted
time: 578ms
memory: 74480kb

Test #46:

score: 0
Accepted
time: 792ms
memory: 83136kb

Test #47:

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

Test #48:

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

Test #49:

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

Test #50:

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

Test #51:

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

Test #52:

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

Test #53:

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

Test #54:

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

Test #55:

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

Test #56:

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

Test #57:

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

Test #58:

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

Test #59:

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

Test #60:

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

Test #61:

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

Test #62:

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

Test #63:

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

Test #64:

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

Test #65:

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

Test #66:

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

Test #67:

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

Test #68:

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

Test #69:

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

Test #70:

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

Test #71:

score: 0
Accepted
time: 75ms
memory: 72864kb

Test #72:

score: 0
Accepted
time: 79ms
memory: 66104kb

Test #73:

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

Test #74:

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

Test #75:

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

Test #76:

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