QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#118605#6639. Disk TreexaphoenixWA 1ms3412kbC++172.6kb2023-07-03 18:57:102023-07-03 18:57:11

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-03 18:57:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3412kb
  • [2023-07-03 18:57:10]
  • 提交

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