QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214271#6639. Disk TreeAlephiaWA 1ms9996kbC++143.1kb2023-10-14 18:23:032023-10-14 18:23:03

Judging History

你现在查看的是最新测评结果

  • [2023-10-14 18:23:03]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:9996kb
  • [2023-10-14 18:23:03]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <queue>
#include <stack>
#include <tuple>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <limits.h>
#include <iostream>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

#define N maxn
#define db double
#define il inline
#define fir first
#define sec second
#define eps (1e-8)
#define pb push_back
#define ll long long
#define mkp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define lowbit(a) (a & (-a))
#define SZ(a) ((int)a.size())
#define ull unsigned long long
#define all(a) a.begin(), a.end()
#define split cout << "=========\n";
#define pll pair<long long, long long>
#define equals(a, b) (fabs((a) - (b)) < eps)

constexpr int ON = 0;
constexpr int CW = -1;
constexpr int CCW = 1;
constexpr int BACK = 2;
constexpr int FRONT = -2;
const db pi = acos(-1.000);
constexpr int maxn = 1e6 + 50;
constexpr int INF = 0x3f3f3f3f;
constexpr ll LINF =  0x3f3f3f3f3f3f3f3f;
constexpr int mod = 998244353; /* 1e9 + 7 */
constexpr int dir[8][2] = {-1, 0, -1, 1, 0, 1, 1, 1, 1, 0, 1, -1, 0, -1, -1, -1};

mt19937_64 rnd(random_device {}());
uniform_int_distribution<ull> dist(0, ULLONG_MAX);//use dist(rnd)

struct ty
{
    ll x,y;
    ll r;
    ll id;
}mas[N],pre[N];
ll n;
ll pf(ll x)
{
    return x*x;
}
double dis(ty a,ty b)
{
    return sqrt(pf(a.x-b.x)*1.0+pf(a.y-b.y)*1.0);
}
ll fa[N];
ll find(ll x)
{
    return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}
bool cmp1(ty a,ty b)
{
    return a.x-a.r<b.x-b.r;
}
bool cmp2(ty a,ty b)
{
    return a.x+a.r<b.x+b.r;
}
bool cmp3(ty a,ty b)
{
    return a.y-a.r<b.y-b.r;
}
bool cmp4(ty a,ty b)
{
    return a.y+a.r<b.y+b.r;
}
struct Edge
{
    ll x,y;
    double val;
}E[N];
bool cmp(Edge a,Edge b)
{
    return a.val<b.val;
}
ll cnt=0;
void init()
{
    for(int i=1;i<n;++i)
    {
        E[++cnt]={mas[i].id,mas[i+1].id,dis(mas[i],mas[i+1])-mas[i].r-mas[i+1].r};
    }
}
struct Ans
{
    ll a,b,c,d;
};
void solve()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>mas[i].x>>mas[i].y>>mas[i].r;
        mas[i].id=i;
        pre[i].x=mas[i].x,pre[i].y=mas[i].y;
    }
    for(int i=1;i<=n;++i) fa[i]=i;
    sort(mas+1,mas+1+n,cmp1);
    init();
    sort(mas+1,mas+1+n,cmp2);
    init();
    sort(mas+1,mas+1+n,cmp3);
    init();
    sort(mas+1,mas+1+n,cmp4);
    init();
    sort(E+1,E+1+cnt,cmp);
    vector<Ans> vt;
    for(int i=1;i<=cnt;++i)
    {
        ll fx=find(E[i].x),fy=find(E[i].y);
        // cout<<E[i].val<<endl;
        if(fx==fy) continue;
        fa[fx]=fy;
        ll x=E[i].x,y=E[i].y;
        vt.push_back({pre[x].x,pre[x].y,pre[y].x,pre[y].y});
    }
    cout<<"YES"<<endl;
    for(auto [a,b,c,d]:vt)
    {
        cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
    }


}

signed main() {
    // cout << fixed << setprecision(10);
    ios::sync_with_stdio(false); cin.tie(nullptr);
    // int T; cin >> T; while (T--)
    solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
1 0 3
10 10 6
0 5 1

output:

YES
1 0 0 5
0 5 10 10

result:

ok answer = 1

Test #2:

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

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

input:

5
10 10 10
2 0 1
20 20 1
3 20 1
20 0 1

output:

YES
3 20 10 10
10 10 2 0
10 10 20 20
20 0 10 10

result:

ok answer = 1

Test #4:

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

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
99 81 98 95
45 88 48 68
17 24 29 29
0 8 17 24
28 55 48 68
17 82 45 88
17 24 28 55
34 0 0 8
45 88 98 95

result:

ok answer = 1

Test #5:

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

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
374 610 304 613
160 703 252 629
119 603 160 703
76 226 95 208
837 286 833 250
776 357 649 305
563 635 459 585
770 417 749 401
47 13 133 115
160 703 116 850
563 635 533 734
422 163 412 265
8 179 47 13
991 604 935 697
841 868 771 828
293 965 235 934
743 97 822 183
683 539 666 460
997 914 910 847
7...

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