QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#118605 | #6639. Disk Tree | xaphoenix | WA | 1ms | 3412kb | C++17 | 2.6kb | 2023-07-03 18:57:10 | 2023-07-03 18:57:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LC k << 1
#define RC k << 1 | 1
#define IO cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define rep(i,a,n) for (int i = a; i < n; i++)
#define repn(i,a,n) for (int i = a; i <= n; i++)
#define per(i,a,n) for (int i = n - 1; i >= a; i--)
#define pern(i,a,n) for (int i = n; i >= a; i--)
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<LL, LL> PLL;
template<typename T> void down(T &x, T y) { if (x > y) x = y; }
const int N = 210000;
const int M = 610000;
const int mod = 998244353;
const int inf = (int)1e9;
const LL INF = (LL)1e12 + 5;
const double eps = 1e-9;
const double pi = acos(-1.0);
struct circle {
LL x, y, r;
bool operator < (const circle& R) const {
if (x == R.x)
return y < R.y;
return x < R.x;
}
}c[N];
struct ed {
LL x, y;
int tp;
bool operator < (const ed& R) const {
if (x == R.x) {
if (y == R.y) return tp > R.tp;
return y < R.y;
}
return x < R.x;
}
};
int n;
vector<ed> a;
set<LL> s;
vector<pair<PLL, PLL>> ans;
int main()
{
IO;
cin >> n;
repn(i, 1, n) {
cin >> c[i].x >> c[i].y >> c[i].r;
ed cur; cur.y = c[i].y;
cur.x = max(c[i].x - c[i].r, (LL)0); cur.tp = 1;
a.pb(cur);
cur.x = c[i].x + c[i].r; cur.tp = -1;
a.pb(cur);
}
sort(all(a));
int l = 0, r = 0, tot = a.size();
PLL last; last.fi = -1;
while (l < tot) {
r = l;
while (r + 1 < tot && a[r + 1].x == a[r].x && a[r + 1].tp == a[r].tp) r ++;
if (a[l].tp > 0) {
int st = 0;
repn(i, l, r) {
auto it = s.upper_bound(a[i].y);
if (s.empty() || it == s.begin()) {
if (last.fi < 0) st = 1;
else {
ans.pb(mp(last, mp(a[i].x, a[i].y)));
last.fi = -1;
}
}
else {
it --; ans.pb(mp(mp(a[i].x, (*it)), mp(a[i].x, a[i].y)));
it ++;
}
if (st == 1 && it != s.end()) {
if (i == r || i != r && (*it) < a[i + 1].y) {
ans.pb(mp(mp(a[i].x, (*it)), mp(a[i].x, a[i].y)));
st = 0;
}
}
s.insert(a[i].y);
}
}
else {
repn(i, l, r) {
s.erase(a[i].y);
if (s.empty()) last = mp(a[i].x, a[i].y);
}
}
l = r + 1;
}
cout << "YES\n";
for (auto it : ans) {
cout << it.fi.fi << " " << it.fi.se << " " << it.se.fi << " " << it.se.se << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3400kb
input:
3 1 0 3 10 10 6 0 5 1
output:
YES 0 0 0 5 4 0 4 10
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 1ms
memory: 3328kb
input:
2 1 1 1 3 3 1
output:
YES 2 1 2 3
result:
ok answer = 1
Test #3:
score: 0
Accepted
time: 0ms
memory: 3380kb
input:
5 10 10 10 2 0 1 20 20 1 3 20 1 20 0 1
output:
YES 1 10 1 0 2 10 2 20 19 10 19 0 19 10 19 20
result:
ok answer = 1
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3412kb
input:
10 29 29 2 28 55 10 99 81 4 17 82 10 45 88 10 48 68 10 0 8 10 98 95 10 34 0 10 17 24 10
output:
YES 7 8 7 24 7 24 7 82 18 24 18 55 24 24 24 0 27 0 27 29 35 55 35 88 38 0 38 68 58 68 88 95 95 95 95 81
result:
wrong answer Two line segments intersect, and it's not only the endpoints that intersect or line segments intersects/touches more than 2 disks