QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#135721#6639. Disk TreePhantomThresholdWA 2ms3608kbC++201.8kb2023-08-05 23:16:142023-08-05 23:16:16

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-05 23:16:16]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3608kb
  • [2023-08-05 23:16:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
struct circ
{
	int x,y,r,id;
	bool operator<(const circ &c)const{return y<c.y;}
};
int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	cin>>n;
	vector<circ> c(n+5);
	vector<pair<int,int>> events;
	for(int i=1;i<=n;i++)
	{
		cin>>c[i].x>>c[i].y>>c[i].r;
		c[i].id=i;
		events.emplace_back(max(c[i].x-c[i].r,0),-i);
		events.emplace_back(c[i].x+c[i].r,i);
	}
	sort(events.begin(),events.end());
	vector<int> pa(n+5);
	function<int(int)> find=[&](int x){return pa[x]?pa[x]=find(pa[x]):x;};
	set<circ> s;
	vector<tuple<int,int,int,int>> ans;
	for(auto [pos,t]:events)
	{
		if(t<0)
		{
			t=-t;
			auto it=s.lower_bound(c[t]);
			if(it!=s.end())
			{
				int pu=find(it->id),pv=find(t);
				if(pu!=pv)
				{
					ans.emplace_back(pos,c[t].y,pos,it->y);
					pa[pv]=pu;
				}
			}
			if(it!=s.begin())
			{
				--it;
				int pu=find(it->id),pv=find(t);
				if(pu!=pv)
				{
					ans.emplace_back(pos,c[t].y,pos,it->y);
					pa[pv]=pu;
				}
			}
			s.insert(c[t]);
		}
		else
		{
			s.erase(c[t]);
		}
	}
	vector<int> minx(n+5,1e9),maxx(n+5,-1e9);
	vector<int> miny(n+5),maxy(n+5);
	for(int i=1;i<=n;i++)
	{
		if(minx[find(i)]>max(c[i].x-c[i].r,0))
			minx[find(i)]=max(c[i].x-c[i].r,0),miny[find(i)]=c[i].y;
		if(maxx[find(i)]<c[i].x+c[i].r)
			maxx[find(i)]=c[i].x+c[i].r,maxy[find(i)]=c[i].y;
	}
	vector<pair<int,int>> srt;
	for(int i=1;i<=n;i++)
	{
		if(find(i)==i)
		{
			srt.emplace_back(minx[i],miny[i]);
			srt.emplace_back(maxx[i],maxy[i]);
		}
	}
	sort(srt.begin(),srt.end());
	for(int i=1;i+1<(int)srt.size();i+=2)
	{
//		cerr<<"fuck "<<endl;
		ans.emplace_back(srt[i].first,srt[i].second,srt[i+1].first,srt[i+1].second);
	}
	cout<<"YES"<<endl;
	for(auto [a,b,c,d]:ans)
		cout<<a<<' '<<b<<' '<<c<<' '<<d<<"\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3480kb

input:

3
1 0 3
10 10 6
0 5 1

output:

YES
0 0 0 5
4 10 4 0

result:

ok answer = 1

Test #2:

score: 0
Accepted
time: 1ms
memory: 3508kb

input:

2
1 1 1
3 3 1

output:

YES
2 3 2 1

result:

ok answer = 1

Test #3:

score: 0
Accepted
time: 1ms
memory: 3532kb

input:

5
10 10 10
2 0 1
20 20 1
3 20 1
20 0 1

output:

YES
1 0 1 10
2 20 2 10
19 0 19 10
19 20 19 10

result:

ok answer = 1

Test #4:

score: 0
Accepted
time: 2ms
memory: 3596kb

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 24 7 8
7 82 7 24
18 55 18 82
24 0 24 24
27 29 27 55
35 88 35 55
38 68 38 88
95 81 95 95
58 68 88 95

result:

ok answer = 1

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3608kb

input:

100
490 783 12
666 460 55
561 245 6
223 323 25
3 520 77
225 161 24
514 190 16
997 914 100
412 265 100
374 610 36
296 854 39
601 901 2
307 21 100
390 422 24
940 414 32
332 438 35
553 992 100
235 775 3
656 901 37
770 417 22
649 305 100
448 84 3
375 939 77
910 847 9
776 357 37
743 97 100
371 502 39
508...

output:

YES
0 13 0 773
0 663 0 773
0 179 0 663
0 366 0 663
0 520 0 663
7 952 7 773
20 607 20 663
39 843 39 952
60 703 60 773
63 850 63 952
64 226 64 366
75 790 75 850
81 208 81 226
100 115 100 208
111 603 111 703
120 512 120 603
129 156 129 366
134 241 134 366
176 100 176 241
179 934 179 703
198 323 198 512...

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