QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#216820 | #2434. Single Cut of Failure | Swarthmore# | AC ✓ | 890ms | 86808kb | C++14 | 6.8kb | 2023-10-16 01:22:47 | 2023-10-16 01:22:48 |
Judging History
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;
}
Details
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