QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#380907 | #2434. Single Cut of Failure | 8BQube# | AC ✓ | 412ms | 38648kb | C++20 | 2.3kb | 2024-04-07 14:50:17 | 2024-04-07 14:50:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())
int n, w, h;
ll hs(ll x, ll y) {
if (y == 0)
return x;
if (x == w)
return w + y;
if (y == h)
return w + h + (w - x);
assert(x == 0);
return w + h + w + (h - y);
}
const double eps = 1e-9;
pair<double, double> rhs(double t) {
if (t >= w + h + w + h)
t -= w + h + w + h;
if (t <= w)
return {t, 0};
t -= w;
if (t <= h)
return {w, t};
t -= h;
if (t <= w)
return {w - t, h};
t -= w;
assert(t <= h);
return {0, h - t};
}
void output(double t) {
t += 0.1;
auto [x, y] = rhs(t);
cout << fixed << setprecision(1) << x << " " << y;
}
const int N = 1e6 + 6;
int cnt[N], cc = 0;
vector<pll> v;
void case1(int l, int r) { // [l, r]
assert(r + 1 < SZ(v));
double a, b;
if (l == 0)
a = 0.1;
else
a = (v[l - 1].X + v[l].X) / 2.0;
b = (v[r].X + v[r + 1].X) / 2.0;
auto [ax, ay] = rhs(a);
auto [bx, by] = rhs(b);
auto both = [&](double x, double y, double c) {
return abs(x - c) < eps && abs(y - c) < eps;
};
if (both(ay, by, 0))
b = w;
else if (both(ax, bx, w))
b = w + h;
else if (both(ay, by, h))
b = w + h + w;
else if (both(ax, bx, 0))
b = 0;
cout << 1 << "\n";
output(a);
cout << " ";
output(b);
cout << "\n";
exit(0);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> w >> h;
for (int i = 0; i < n; i++) {
for (int j = 0; j < 2; j++) {
int x, y;
cin >> x >> y;
v.pb({hs(x, y), i});
}
}
sort(ALL(v));
assert(SZ(v) == 2 * n);
for (int i = 0; i < SZ(v); i++) {
cnt[v[i].Y]++;
if (cnt[v[i].Y] == 1)
cc++;
if (i - n >= 0) {
cnt[v[i - n].Y]--;
if (cnt[v[i - n].Y] == 0)
--cc;
}
if (cc == n)
case1(i - n + 1, i);
}
cout << 2 << "\n";
output(0); cout << " "; output(w + h); cout << "\n";
output(w); cout << " "; output(w + h + w); cout << "\n";
}
Details
Test #1:
score: 100
Accepted
time: 1ms
memory: 3844kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 3892kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 3924kb
Test #4:
score: 0
Accepted
time: 0ms
memory: 3864kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 3844kb
Test #6:
score: 0
Accepted
time: 0ms
memory: 3916kb
Test #7:
score: 0
Accepted
time: 0ms
memory: 3912kb
Test #8:
score: 0
Accepted
time: 1ms
memory: 3728kb
Test #9:
score: 0
Accepted
time: 91ms
memory: 12172kb
Test #10:
score: 0
Accepted
time: 81ms
memory: 12096kb
Test #11:
score: 0
Accepted
time: 92ms
memory: 12120kb
Test #12:
score: 0
Accepted
time: 95ms
memory: 12084kb
Test #13:
score: 0
Accepted
time: 86ms
memory: 12172kb
Test #14:
score: 0
Accepted
time: 87ms
memory: 12172kb
Test #15:
score: 0
Accepted
time: 93ms
memory: 12184kb
Test #16:
score: 0
Accepted
time: 92ms
memory: 12128kb
Test #17:
score: 0
Accepted
time: 89ms
memory: 12228kb
Test #18:
score: 0
Accepted
time: 85ms
memory: 12176kb
Test #19:
score: 0
Accepted
time: 91ms
memory: 12060kb
Test #20:
score: 0
Accepted
time: 89ms
memory: 12116kb
Test #21:
score: 0
Accepted
time: 95ms
memory: 12260kb
Test #22:
score: 0
Accepted
time: 94ms
memory: 12156kb
Test #23:
score: 0
Accepted
time: 96ms
memory: 12116kb
Test #24:
score: 0
Accepted
time: 404ms
memory: 38648kb
Test #25:
score: 0
Accepted
time: 412ms
memory: 38648kb
Test #26:
score: 0
Accepted
time: 0ms
memory: 3908kb
Test #27:
score: 0
Accepted
time: 0ms
memory: 3912kb
Test #28:
score: 0
Accepted
time: 1ms
memory: 3940kb
Test #29:
score: 0
Accepted
time: 0ms
memory: 4064kb
Test #30:
score: 0
Accepted
time: 7ms
memory: 4376kb
Test #31:
score: 0
Accepted
time: 343ms
memory: 36100kb
Test #32:
score: 0
Accepted
time: 403ms
memory: 38456kb
Test #33:
score: 0
Accepted
time: 1ms
memory: 3864kb
Test #34:
score: 0
Accepted
time: 1ms
memory: 3908kb
Test #35:
score: 0
Accepted
time: 1ms
memory: 3944kb
Test #36:
score: 0
Accepted
time: 4ms
memory: 4036kb
Test #37:
score: 0
Accepted
time: 8ms
memory: 4268kb
Test #38:
score: 0
Accepted
time: 62ms
memory: 11508kb
Test #39:
score: 0
Accepted
time: 380ms
memory: 38500kb
Test #40:
score: 0
Accepted
time: 1ms
memory: 3864kb
Test #41:
score: 0
Accepted
time: 0ms
memory: 3972kb
Test #42:
score: 0
Accepted
time: 1ms
memory: 3996kb
Test #43:
score: 0
Accepted
time: 3ms
memory: 4088kb
Test #44:
score: 0
Accepted
time: 30ms
memory: 7268kb
Test #45:
score: 0
Accepted
time: 259ms
memory: 36216kb
Test #46:
score: 0
Accepted
time: 376ms
memory: 38568kb
Test #47:
score: 0
Accepted
time: 1ms
memory: 3912kb
Test #48:
score: 0
Accepted
time: 1ms
memory: 3920kb
Test #49:
score: 0
Accepted
time: 0ms
memory: 3876kb
Test #50:
score: 0
Accepted
time: 0ms
memory: 3872kb
Test #51:
score: 0
Accepted
time: 0ms
memory: 3784kb
Test #52:
score: 0
Accepted
time: 1ms
memory: 3872kb
Test #53:
score: 0
Accepted
time: 0ms
memory: 3924kb
Test #54:
score: 0
Accepted
time: 0ms
memory: 3964kb
Test #55:
score: 0
Accepted
time: 1ms
memory: 3924kb
Test #56:
score: 0
Accepted
time: 0ms
memory: 3860kb
Test #57:
score: 0
Accepted
time: 0ms
memory: 3896kb
Test #58:
score: 0
Accepted
time: 1ms
memory: 3968kb
Test #59:
score: 0
Accepted
time: 0ms
memory: 3920kb
Test #60:
score: 0
Accepted
time: 0ms
memory: 3908kb
Test #61:
score: 0
Accepted
time: 0ms
memory: 3920kb
Test #62:
score: 0
Accepted
time: 1ms
memory: 3912kb
Test #63:
score: 0
Accepted
time: 0ms
memory: 3868kb
Test #64:
score: 0
Accepted
time: 0ms
memory: 3912kb
Test #65:
score: 0
Accepted
time: 0ms
memory: 3916kb
Test #66:
score: 0
Accepted
time: 0ms
memory: 3924kb
Test #67:
score: 0
Accepted
time: 1ms
memory: 3936kb
Test #68:
score: 0
Accepted
time: 0ms
memory: 3860kb
Test #69:
score: 0
Accepted
time: 1ms
memory: 3920kb
Test #70:
score: 0
Accepted
time: 0ms
memory: 3724kb
Test #71:
score: 0
Accepted
time: 31ms
memory: 7292kb
Test #72:
score: 0
Accepted
time: 14ms
memory: 7252kb
Test #73:
score: 0
Accepted
time: 24ms
memory: 7332kb
Test #74:
score: 0
Accepted
time: 35ms
memory: 7444kb
Test #75:
score: 0
Accepted
time: 22ms
memory: 7352kb
Test #76:
score: 0
Accepted
time: 1ms
memory: 3924kb