QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#373070 | #2434. Single Cut of Failure | TWTP_TCTF | AC ✓ | 312ms | 64664kb | C++14 | 6.1kb | 2024-04-01 01:48:46 | 2024-04-01 01:48:47 |
Judging History
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