QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#373070#2434. Single Cut of FailureTWTP_TCTFAC ✓312ms64664kbC++146.1kb2024-04-01 01:48:462024-04-01 01:48:47

Judging History

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

  • [2024-04-01 01:48:47]
  • 评测
  • 测评结果:AC
  • 用时:312ms
  • 内存:64664kb
  • [2024-04-01 01:48:46]
  • 提交

answer

#include<iostream>
#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
const int N = 2e6 + 2, MOD = 998244353;
ld eps = 1e-5;

struct pt {
    long long x, y;

    pt() {}

    pt(long long _x, long long _y) : x(_x), y(_y) {}

    pt operator-(const pt &p) const { return pt(x - p.x, y - p.y); }

    long long cross(const pt &p) const { return x * p.y - y * p.x; }

    long long cross(const pt &a, const pt &b) const { return (a - *this).cross(b - *this); }
};

int sgn(const long long &x) { return x >= 0 ? x ? 1 : 0 : -1; }

bool inter1(long long a, long long b, long long c, long long d) {
    if (a > b)
        swap(a, b);
    if (c > d)
        swap(c, d);
    return max(a, c) <= min(b, d);
}

bool check_inter(const pt &a, const pt &b, const pt &c, const pt &d) {
    if (c.cross(a, d) == 0 && c.cross(b, d) == 0)
        return inter1(a.x, b.x, c.x, d.x) && inter1(a.y, b.y, c.y, d.y);
    return sgn(a.cross(b, c)) != sgn(a.cross(b, d)) &&
           sgn(c.cross(d, a)) != sgn(c.cross(d, b));
}

vector<pair<pt, pt>> v;

bool check(pt a, pt b) {
    for (auto i: v) {
        if (!check_inter(a, b, i.first, i.second))return false;
    }
    return true;
}

vector<ld> solve(int w, int h) {
    ll l1 = 0, r1 = h, l2 = 0, r2 = h;

    for (int i = 0; i < v.size(); i++) {
        if (v[i].first.x > v[i].second.x)swap(v[i].first, v[i].second);
    }

    vector<pair<ll, ll> > rem;
    for (auto i: v) {
        if (i.first.x > 0 && i.second.x < w)continue;

        if (i.first.x == 0 && i.second.y == h) {
            l1 = max(l1, i.first.y);
        } else if (i.first.x == 0 && i.second.y == 0) {
            r1 = min(r1, i.first.y);
        } else if (i.first.x == 0) {
            rem.push_back({i.first.y, i.second.y});
        } else if (i.first.y == h) {
            l2 = max(l2, i.second.y);
        } else if (i.first.y == 0) {
            r2 = min(r2, i.second.y);
        } else {
            assert(false);
        }
    }
    if (l1 >= r1 || l2 >= r2)return {};

    if (rem.empty()) {
        return {0, l1 + eps, (ld) w, l2 + eps};
    }

    sort(rem.begin(), rem.end());
    stack<ll> st;
    st.push(0);

    for (int i = rem.size() - 1; i >= 0; i--) {
        st.push(max(st.top(), rem[i].second));
    }

    if (rem[0].first > l1 && st.top() < r2) {
        return {0, l1 + eps, (ld) w, r2 - eps};
    }

    for (int i = 0; i < rem.size(); i++) {
        st.pop();
        l1 = max(l1, rem[i].first);
        r2 = min(r2, rem[i].second);
        if (l1 >= r1 || l2 >= r2)return {};

        if (i + 1 < rem.size() && rem[i + 1].first <= l1)continue;

        if (st.top() < r2) {
            return {0, l1 + eps, (ld) w, r2 - eps};
        }
    }
    return {};
}

int getID(pt a, int w, int h) {
    if (a.y == h) return 1;
    if (a.x == w)return 2;
    if (a.y == 0)return 3;
    return 4;
}

vector<ld> solve2(int w, int h) {
    ll l1 = 0, r1 = w, l2 = 0, r2 = h;


    vector<pair<ll, ll> > rem;
    for (auto &i: v) {
        int a = getID(i.first, w, h), b = getID(i.second, w, h);
        if (a > b) {
            swap(a, b);
            swap(i.first, i.second);
        }

        if (a == 1 && b == 2) {
            rem.push_back({i.first.x, i.second.y});
        } else if (a == 1 && (b >= 3)) {
            r1 = min(r1, i.first.x);
        } else if (a == 2) {
            r2 = min(r2, i.first.y);
        } else if (a == 3) {
            return {};
        }
    }

    if (rem.empty()) {
        return {l1 + eps, (ld) h, (ld) w, l2 + eps};
    }

    sort(rem.begin(), rem.end());
    stack<ll> st;
    st.push(0);

    for (int i = rem.size() - 1; i >= 0; i--) {
        st.push(max(st.top(), rem[i].second));
    }

    if (rem[0].first > l1 && st.top() < r2) {
        return {l1 + eps, (ld) h, (ld) w, r2 - eps};
    }

    for (int i = 0; i < rem.size(); i++) {
        st.pop();
        l1 = max(l1, rem[i].first);
        r2 = min(r2, rem[i].second);
        if (l1 >= r1 || l2 >= r2)return {};

        if (i + 1 < rem.size() && rem[i + 1].first <= l1)continue;

        if (st.top() < r2) {
            return {l1 + eps, (ld) h, (ld) w, r2 - eps};
        }
    }
    return {};
}

void rotateLeft(ll &x, ll &y, int w, int h) {
    swap(x, y);
    x = h - x;
}

void rotateLeft(ld &x, ld &y, int w, int h) {
    swap(x, y);
    x = h - x;
}

void doWork() {
    int n, w, h;
    cin >> n >> w >> h;
    for (int i = 0; i < n; i++) {
        pt a, b;
        cin >> a.x >> a.y;
        cin >> b.x >> b.y;

        v.push_back({a, b});
    }
    if (check({0, 0}, {w, h})) {
        cout << "1\n";
        cout << fixed << eps << " " << 0 << " " << w - eps << " " << h;
        return;
    }
    if (check({0, h}, {w, 0})) {
        cout << "1\n";
        cout << fixed << eps << " " << h << " " << w - eps << " " << 0;
        return;
    }

    for (int k = 0; k < 4; k++) {
        vector<ld> temp = solve(w, h);
        if (temp.empty()) temp = solve2(w, h);

        if (!temp.empty()) {
            cout << "1\n";
            int temp_w = w, temp_h = h;
            for (int z = 0; z < 4 - k; z++) {
                rotateLeft(temp[0], temp[1], temp_w, temp_h);
                rotateLeft(temp[2], temp[3], temp_w, temp_h);
                swap(temp_w, temp_h);
            }
            for (auto i: temp)cout << fixed << i << " ";
            return;
        }

        for (int i = 0; i < v.size(); i++) {
            rotateLeft(v[i].first.x, v[i].first.y, w, h);
            rotateLeft(v[i].second.x, v[i].second.y, w, h);
        }
        swap(w, h);
    }

    cout << "2\n";
    cout << fixed << eps << " " << 0 << " " << w - eps << " " << h;
    cout << "\n";
    cout << fixed << eps << " " << h << " " << w - eps << " " << 0;
}

int main() {
    IO
    int t = 1;
//    cin >> t;
    for (int i = 1; i <= t; i++) {
        //  cout << "Case #" << i << ": ";
        doWork();
    }
}

Details

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 0
Accepted
time: 41ms
memory: 13088kb

Test #10:

score: 0
Accepted
time: 32ms
memory: 12424kb

Test #11:

score: 0
Accepted
time: 58ms
memory: 13204kb

Test #12:

score: 0
Accepted
time: 55ms
memory: 13232kb

Test #13:

score: 0
Accepted
time: 46ms
memory: 12160kb

Test #14:

score: 0
Accepted
time: 66ms
memory: 13312kb

Test #15:

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

Test #16:

score: 0
Accepted
time: 57ms
memory: 12760kb

Test #17:

score: 0
Accepted
time: 70ms
memory: 12772kb

Test #18:

score: 0
Accepted
time: 49ms
memory: 12432kb

Test #19:

score: 0
Accepted
time: 58ms
memory: 11556kb

Test #20:

score: 0
Accepted
time: 53ms
memory: 12352kb

Test #21:

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

Test #22:

score: 0
Accepted
time: 57ms
memory: 15008kb

Test #23:

score: 0
Accepted
time: 60ms
memory: 13160kb

Test #24:

score: 0
Accepted
time: 264ms
memory: 49572kb

Test #25:

score: 0
Accepted
time: 312ms
memory: 48764kb

Test #26:

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

Test #27:

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

Test #28:

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

Test #29:

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

Test #30:

score: 0
Accepted
time: 9ms
memory: 4116kb

Test #31:

score: 0
Accepted
time: 238ms
memory: 37736kb

Test #32:

score: 0
Accepted
time: 272ms
memory: 41764kb

Test #33:

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

Test #34:

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

Test #35:

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

Test #36:

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

Test #37:

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

Test #38:

score: 0
Accepted
time: 48ms
memory: 13476kb

Test #39:

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

Test #40:

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

Test #41:

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

Test #42:

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

Test #43:

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

Test #44:

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

Test #45:

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

Test #46:

score: 0
Accepted
time: 268ms
memory: 64664kb

Test #47:

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

Test #48:

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

Test #49:

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

Test #50:

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

Test #51:

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

Test #52:

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

Test #53:

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

Test #54:

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

Test #55:

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

Test #56:

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

Test #57:

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

Test #58:

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

Test #59:

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

Test #60:

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

Test #61:

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

Test #62:

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

Test #63:

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

Test #64:

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

Test #65:

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

Test #66:

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

Test #67:

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

Test #68:

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

Test #69:

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

Test #70:

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

Test #71:

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

Test #72:

score: 0
Accepted
time: 21ms
memory: 7460kb

Test #73:

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

Test #74:

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

Test #75:

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

Test #76:

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