QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#123541#6639. Disk TreeinstallbWA 2ms9612kbC++142.1kb2023-07-12 20:23:312023-07-12 20:23:32

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-12 20:23:32]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9612kb
  • [2023-07-12 20:23:31]
  • 提交

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]});
    }
    
    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({x[s[i - 1].id] + r[s[i - 1].id],y[s[i - 1].id],x[u] - r[u],y[u]});
        else ans.push_back({x[id],y[id],x[u],y[u]});
        st.insert({y[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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 7544kb

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: 1ms
memory: 7536kb

input:

2
1 1 1
3 3 1

output:

YES
1 1 3 3

result:

ok answer = 1

Test #3:

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

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: 0
Accepted
time: 2ms
memory: 9612kb

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
58 68 88 95
98 95 99 81

result:

ok answer = 1

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 9604kb

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 179
0 179 0 366
0 366 0 520
0 520 0 663
0 663 0 773
32 773 67 952
29 663 35 607
67 952 51 843
32 773 160 703
67 952 116 850
92 366 76 226
116 850 81 790
76 226 95 208
95 208 133 115
160 703 119 603
119 603 204 512
92 366 137 156
92 366 195 241
195 241 205 100
160 703 235 934
204 512 223 3...

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