QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#135720 | #6639. Disk Tree | PhantomThreshold | WA | 1ms | 3480kb | C++20 | 1.8kb | 2023-08-05 23:14:44 | 2023-08-05 23:14:47 |
Judging History
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(c[i].x-c[i].r,-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)]>c[i].x-c[i].r)
minx[find(i)]=c[i].x-c[i].r,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: 0
Wrong Answer
time: 1ms
memory: 3480kb
input:
3 1 0 3 10 10 6 0 5 1
output:
YES -1 5 -1 0 4 10 4 0
result:
wrong answer Integer element x_1,y_1,x_2,y_2[1] equals to -1, violates the range [0, 10^9]