QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#119118#6639. Disk Treeideograph_advantageWA 1ms3508kbC++173.3kb2023-07-04 23:31:322023-07-04 23:31:33

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-04 23:31:33]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3508kb
  • [2023-07-04 23:31:32]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0);
#define iter(a) a.begin(), a.end()
#define pb(a) emplace_back(a)
#define mp(a, b) make_pair(a, b)
#define ff first
#define ss second
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define SZ(a) int(a.size())
#ifdef LOCAL
void debug(){cerr << "\n";}
template<class T, class ... U> void debug(T a, U ... b){cerr << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cerr << *l << " ", l++;
	cerr << "\n";
}
#else
#define debug(...) void()
#define pary(...) void()
#endif

typedef long long ll;
//typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.ff << ',' << p.ss << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

struct event{
    int x, y, ty;
    bool operator<(event b){
        if(x != b.x) return x < b.x;
        if(ty != b.ty) return ty > b.ty;
        return y < b.y;
    }
};

int main(){
    StarBurstStream;

    int n;
    cin >> n;

    vector<event> ev;
    for(int i = 0; i < n; i++){
        int x, y, r;
        cin >> x >> y >> r;
        ev.pb(event({x - r, y, 1}));
        ev.pb(event({x + r, y, -1}));
    }
    sort(iter(ev));
    
    set<int> st;
    pii lst = mp(-1, -1);
    vector<pair<pii, pii>> ans;
    for(int i = 0; i < 2 * n; ){
        int x = ev[i].x;
        vector<int> tmp;
        for(; i < 2 * n && ev[i].x == x && ev[i].ty == 1; i++){
            tmp.pb(ev[i].y);
            st.insert(ev[i].y);
        }
        //debug("test", x);
        //if(i < 2 * n) debug("OAO", ev[i].x, ev[i].y, ev[i].ty);
        //pary(iter(tmp));
        //pary(iter(st));
        bool up = false;
        for(int j = 0; j < SZ(tmp); j++){
            int y = tmp[j];
            auto it = st.find(y);
            if(it != st.begin() && (j && *prev(it) != tmp[j - 1])) up = false;
            if(!up && it != st.begin()){
                ans.pb(mp(mp(x, *prev(it)), mp(x, y)));
                //debug("pb", y, mp(x, *prev(it)));
            }
            else if(next(it) != st.end()){
                ans.pb(mp(mp(x, *next(it)), mp(x, y)));
                up = true;
                //debug("pb", y, mp(x, *next(it)));
            }
            else if(lst != mp(-1, -1)){
                ans.pb(mp(lst, mp(x, y)));
                //debug("pb", lst);
            }
        }
        for(; i < 2 * n && ev[i].x == x && ev[i].ty == -1; i++){
            st.erase(ev[i].y);
            lst = mp(x, ev[i].y);
        }
        //debug("ok", x);
        //if(i < 2 * n) debug("OAO", ev[i].x, ev[i].y, ev[i].ty);
    }

    cout << "YES\n";
    for(auto [a, b] : ans){
        a.ff = max(a.ff, 0);
        b.ff = max(b.ff, 0);
        cout << a.ff << " " << a.ss << " " << b.ff << " " << b.ss << "\n";
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3448kb

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: 3504kb

input:

2
1 1 1
3 3 1

output:

YES
2 1 2 3

result:

ok answer = 1

Test #3:

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

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

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

result:

ok answer = 1

Test #5:

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

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

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