QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#119116#6639. Disk Treeideograph_advantageWA 1ms3468kbC++173.1kb2023-07-04 23:15:462023-07-04 23:15:50

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:15:50]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3468kb
  • [2023-07-04 23:15:46]
  • 提交

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(y != b.y) return y < b.y;
        return ty > b.ty;
    }
};

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);
        //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);
        }
    }

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

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

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

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: -100
Wrong Answer
time: 0ms
memory: 3412kb

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