QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#123547 | #6639. Disk Tree | installb | WA | 2ms | 7528kb | C++14 | 2.2kb | 2023-07-12 20:33:32 | 2023-07-12 20:33:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 400005;
struct interval{
int l,r,id;
bool operator < (const interval &o)const{
return l < o.l;
}
}s[N];
set <pair <int,int> > st;
vector <tuple <int,int,int,int> > ans;
int n,x[N],y[N],r[N];
void solve(){
cin >> n;
for(int i = 1;i <= n;i ++){
cin >> x[i] >> y[i] >> r[i];
s[i] = {x[i] - r[i],x[i] + r[i],i};
}
sort(s + 1,s + 1 + n);
// x has to be >= 0, so connect all possible circles with x = 0 first
int pos = 0;
for(int i = 1;i <= n;i ++){
if(x[s[i].id] - r[s[i].id] <= 0) pos = i;
else break;
}
vector <pair <int,int> > G;
for(int i = 1;i <= pos;i ++){
G.push_back({y[s[i].id],s[i].id});
st.insert({y[s[i].id],s[i].id});
}
sort(G.begin(),G.end());
for(int i = 1;i < G.size();i ++){
int u = G[i - 1].second,v = G[i].second;
ans.push_back({0,y[u],0,y[v]});
}
pair <int,int> mxr = {-1,-1};
for(int i = 1;i <= pos;i ++) mxr = max(mxr,{x[s[i].id] + r[s[i].id],s[i].id});
for(int i = pos + 1;i <= n;i ++){
int u = s[i].id,id = -1;
while(st.size()){
auto it = st.lower_bound({y[u],-1});
if(it == st.end()) break;
int v = it->second;
if(x[v] + r[v] < x[u] - r[u]) st.erase(it);
else{
id = v;
break;
}
}
if(id == -1){
while(st.size()){
auto it = -- st.lower_bound({y[u],-1});
int v = it->second;
if(x[v] + r[v] < x[u] - r[u]) st.erase(it);
else{
id = v;
break;
}
}
}
if(id == -1 && i > 1) ans.push_back({mxr.second,y[mxr.first],x[u] - r[u],y[u]});
else ans.push_back({x[id],y[id],x[u],y[u]});
st.insert({y[u],u});
mxr = max(mxr,{x[u] + r[u],u});
}
cout << "YES\n";
for(auto [a,b,c,d] : ans) cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
}
int main(){
ios::sync_with_stdio(false);
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7508kb
input:
3 1 0 3 10 10 6 0 5 1
output:
YES 0 0 0 5 1 0 10 10
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 2ms
memory: 7528kb
input:
2 1 1 1 3 3 1
output:
YES 1 1 3 3
result:
ok answer = 1
Test #3:
score: 0
Accepted
time: 2ms
memory: 7508kb
input:
5 10 10 10 2 0 1 20 20 1 3 20 1 20 0 1
output:
YES 10 10 2 0 10 10 3 20 10 10 20 20 10 10 20 0
result:
ok answer = 1
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 7504kb
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 0 8 17 82 17 82 17 24 17 82 28 55 17 24 34 0 28 55 29 29 28 55 45 88 45 88 48 68 6 0 88 95 98 95 99 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