QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#113505 | #6639. Disk Tree | Hegdahl | WA | 5ms | 4096kb | C++20 | 6.0kb | 2023-06-18 09:26:43 | 2023-06-18 09:26:47 |
Judging History
answer
#include <bits/stdc++.h>
// <graph/ufds.hpp>
#include <optional>
#include <utility>
#include <vector>
template <class Container = std::vector<int>, bool path_compression = true>
struct UFDS {
Container a;
UFDS(int n) : a(n, -1) {}
int find(int i) {
if constexpr (path_compression) {
return a[i] < 0 ? i : a[i] = find(a[i]);
} else {
while (a[i] >= 0) i = a[i];
return i;
}
}
std::optional<std::pair<int, int>> unite(int i, int j) {
i = find(i), j = find(j);
if (i == j) return std::nullopt;
if (-a[i] < -a[j]) std::swap(i, j);
a[i] = a[i] + a[j];
a[j] = i;
return std::make_pair(i, j);
}
};
// </graph/ufds.hpp>
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
using std::ostream;
using std::vector;
using std::tie;
template<class T>
auto sz(T &&x) -> int {
return static_cast<int>(std::size(x));
}
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x_=0, T y_=0) : x(x_), y(y_) {}
bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
P operator+(P p) const { return P(x+p.x, y+p.y); }
P operator-(P p) const { return P(x-p.x, y-p.y); }
P operator*(T d) const { return P(x*d, y*d); }
P operator/(T d) const { return P(x/d, y/d); }
T dot(P p) const { return x*p.x + y*p.y; }
T cross(P p) const { return x*p.y - y*p.x; }
T cross(P a, P b) const { return (a-*this).cross(b-*this); }
T dist2() const { return x*x + y*y; }
double dist() const { return sqrt((double)dist2()); }
// angle to x-axis in interval [-pi, pi]
double angle() const { return atan2(y, x); }
P unit() const { return *this/dist(); } // makes dist()=1
P perp() const { return P(-y, x); } // rotates +90 degrees
P normal() const { return perp().unit(); }
// returns point rotated 'a' radians ccw around the origin
P rotate(double a) const {
return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
friend ostream& operator<<(ostream& os, P p) {
return os << "(" << p.x << "," << p.y << ")"; }
};
template<class T> struct Point3D {
typedef Point3D P;
typedef const P& R;
T x, y, z;
explicit Point3D(T x_=0, T y_=0, T z_=0) : x(x_), y(y_), z(z_) {}
bool operator<(R p) const {
return tie(x, y, z) < tie(p.x, p.y, p.z); }
bool operator==(R p) const {
return tie(x, y, z) == tie(p.x, p.y, p.z); }
P operator+(R p) const { return P(x+p.x, y+p.y, z+p.z); }
P operator-(R p) const { return P(x-p.x, y-p.y, z-p.z); }
P operator*(T d) const { return P(x*d, y*d, z*d); }
P operator/(T d) const { return P(x/d, y/d, z/d); }
T dot(R p) const { return x*p.x + y*p.y + z*p.z; }
P cross(R p) const {
return P(y*p.z - z*p.y, z*p.x - x*p.z, x*p.y - y*p.x);
}
T dist2() const { return x*x + y*y + z*z; }
double dist() const { return sqrt((double)dist2()); }
//Azimuthal angle (longitude) to x-axis in interval [-pi, pi]
double phi() const { return atan2(y, x); }
//Zenith angle (latitude) to the z-axis in interval [0, pi]
double theta() const { return atan2(sqrt(x*x+y*y),z); }
P unit() const { return *this/(T)dist(); } //makes dist()=1
//returns unit vector normal to *this and p
P normal(P p) const { return cross(p).unit(); }
//returns point rotated 'angle' radians ccw around axis
P rotate(double angle, P axis) const {
double s = sin(angle), c = cos(angle); P u = axis.unit();
return u*dot(u)*(1-c) + (*this)*c - cross(u)*s;
}
};
typedef Point3D<double> P3;
struct PR {
void ins(int x) { (a == -1 ? a : b) = x; }
void rem(int x) { (a == x ? a : b) = -1; }
int cnt() { return (a != -1) + (b != -1); }
int a, b;
};
struct F { P3 q; int a, b, c; };
vector<F> hull3d(const vector<P3>& A) {
assert(sz(A) >= 4);
vector<vector<PR>> E(sz(A), vector<PR>(sz(A), {-1, -1}));
#define E(x,y) E[f.x][f.y]
vector<F> FS;
auto mf = [&](int i, int j, int k, int l) {
P3 q = (A[j] - A[i]).cross((A[k] - A[i]));
if (q.dot(A[l]) > q.dot(A[i]))
q = q * -1;
F f{q, i, j, k};
E(a,b).ins(k); E(a,c).ins(j); E(b,c).ins(i);
FS.push_back(f);
};
rep(i,0,4) rep(j,i+1,4) rep(k,j+1,4)
mf(i, j, k, 6 - i - j - k);
rep(i,4,sz(A)) {
rep(j,0,sz(FS)) {
F f = FS[j];
if(f.q.dot(A[i]) > f.q.dot(A[f.a])) {
E(a,b).rem(f.c);
E(a,c).rem(f.b);
E(b,c).rem(f.a);
std::swap(FS[j--], FS.back());
FS.pop_back();
}
}
int nw = sz(FS);
rep(j,0,nw) {
F f = FS[j];
#define C(a, b, c) if (E(a,b).cnt() != 2) mf(f.a, f.b, i, f.c);
C(a, b, c); C(a, c, b); C(b, c, a);
}
}
for (F& it : FS) if ((A[it.b] - A[it.a]).cross(
A[it.c] - A[it.a]).dot(it.q) <= 0) std::swap(it.c, it.b);
return FS;
};
template<class P, class F>
void delaunay(vector<P>& ps, F trifun) {
if (sz(ps) == 3) { int d = (ps[0].cross(ps[1], ps[2]) < 0);
trifun(0,1+d,2-d); }
vector<P3> p3;
for (P p : ps) p3.emplace_back(p.x, p.y, p.dist2());
if (sz(ps) > 3) for(auto t:hull3d(p3)) if ((p3[t.b]-p3[t.a]).
cross(p3[t.c]-p3[t.a]).dot(P3(0,0,1)) < 0)
trifun(t.a, t.c, t.b);
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int n; std::cin >> n;
std::vector<int> radii(n);
vector<Point<int>> centers(n);
for (int i = 0; i < n; ++i) {
std::cin >> centers[i].x >> centers[i].y >> radii[i];
}
vector<std::tuple<double, int, int>> edges;
auto add_edge = [&](int i, int j) {
double d = (centers[i] - centers[j]).dist();
edges.emplace_back(d, i, j);
};
if (n <= 1000) {
for (int i = 0; i < n; ++i) {
for (int j = i+1; j < n; ++j) {
add_edge(i, j);
}
}
} else {
delaunay(centers, [&](int a, int b, int c) {
add_edge(a, b);
add_edge(b, c);
add_edge(c, a);
});
}
std::sort(edges.begin(), edges.end());
auto uf = UFDS(n);
std::cout << "YES\n";
for (auto [d, i, j] : edges) {
if (uf.unite(i, j)) {
std::cout << centers[i].x << ' ' << centers[i].y << " " << centers[j].x << ' ' << centers[j].y << "\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3556kb
input:
3 1 0 3 10 10 6 0 5 1
output:
YES 1 0 0 5 10 10 0 5
result:
ok answer = 1
Test #2:
score: 0
Accepted
time: 1ms
memory: 3444kb
input:
2 1 1 1 3 3 1
output:
YES 1 1 3 3
result:
ok answer = 1
Test #3:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
5 10 10 10 2 0 1 20 20 1 3 20 1 20 0 1
output:
YES 10 10 3 20 10 10 2 0 10 10 20 20 10 10 20 0
result:
ok answer = 1
Test #4:
score: 0
Accepted
time: 0ms
memory: 3452kb
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 29 29 17 24 99 81 98 95 45 88 48 68 0 8 17 24 28 55 48 68 29 29 28 55 17 82 45 88 34 0 17 24 99 81 48 68
result:
ok answer = 1
Test #5:
score: 0
Accepted
time: 1ms
memory: 3592kb
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 267 249 255 263 95 208 76 226 770 417 749 401 951 132 975 153 833 250 837 286 865 52 897 76 137 156 133 115 448 84 447 40 533 734 493 714 770 417 814 404 833 250 787 237 982 709 935 697 267 249 290 204 809 794 771 828 776 357 749 401 81 790 32 773 742 210 787 237 252 629 304 613 601 901 656 901 ...
result:
ok answer = 1
Test #6:
score: 0
Accepted
time: 3ms
memory: 3720kb
input:
200 2948 9798 687 3897 647 35 3918 587 28 1262 2717 206 1315 9524 20 2381 305 1000 4344 6858 20 6234 8949 53 5168 4772 85 5044 6109 158 72 7670 132 7300 1213 837 5427 2263 1000 1785 3009 276 6136 1421 43 1629 5620 29 6445 9489 242 8443 3141 1000 4118 4307 63 1874 5238 291 1964 5785 73 7794 3934 18 3...
output:
YES 3897 647 3918 587 3524 778 3427 769 9514 2928 9434 2844 2981 8806 2975 8690 8791 6984 8868 7083 4010 5036 3881 5104 462 9493 413 9349 6062 9827 6125 9979 4231 3772 4084 3848 449 1890 602 1954 3446 602 3427 769 5044 6109 4946 6252 9881 5238 9965 5083 3897 647 3984 820 6136 1421 6334 1443 3076 661...
result:
ok answer = 1
Test #7:
score: -100
Wrong Answer
time: 5ms
memory: 4096kb
input:
300 42942 37079 222 49441 21821 1695 61023 31153 561 86630 26307 352 36940 78253 213 7841 81086 626 47425 22290 374 17694 68695 648 38259 64794 998 43599 46942 9662 9204 2816 1965 38652 83568 4057 4046 29001 1034 72591 63214 587 75984 64859 1112 70005 72177 576 34522 52126 652 56627 48785 1747 78820...
output:
YES 97975 50437 97653 50419 27055 9398 831 69461 38259 64794 95387 32673 59314 96287 27055 9398 79578 74740 80752 9209 89929 80246 89194 79757 54429 19028 65601 83613 79578 74740 80460 74194 61023 31153 6790 67963 48642 86091 49759 86207 86630 26307 8017 75412 908 79893 66345 83699 84285 54633 83971...
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