QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214271 | #6639. Disk Tree | Alephia | WA | 1ms | 9996kb | C++14 | 3.1kb | 2023-10-14 18:23:03 | 2023-10-14 18:23:03 |
Judging History
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;
}
详细
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