QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#113503 | #6639. Disk Tree | Hegdahl | WA | 2ms | 3740kb | C++20 | 6.0kb | 2023-06-18 09:24:00 | 2023-06-18 09:24:01 |
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() - radii[i] - radii[j];
edges.emplace_back(d, i, j);
};
if (n <= 10) {
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";
}
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3484kb
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: 3484kb
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: 3460kb
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: 1ms
memory: 3464kb
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 29 29 17 24 0 8 17 24 28 55 48 68 17 82 45 88 34 0 17 24 28 55 17 24 45 88 98 95
result:
ok answer = 1
Test #5:
score: 0
Accepted
time: 1ms
memory: 3620kb
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 649 305 560 422 375 939 468 868 743 97 742 210 204 512 92 366 448 84 447 40 307 21 205 100 837 286 964 284 811 693 809 794 375 939 293 965 981 11 865 52 296 854 375 939 374 610 304 613 252 629 160 703 445 639 563 635 899 204 964 284 119 603 160 703 508 524 458 464 67 952 116 850 95 208 76 226 13...
result:
ok answer = 1
Test #6:
score: 0
Accepted
time: 2ms
memory: 3616kb
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 3841 6121 4160 6939 1566 4450 1828 4099 5710 4771 5901 4668 7300 1213 6334 1443 4278 321 4775 842 4344 6858 4160 6939 4718 3379 4284 3385 9446 2407 9940 2103 8040 7929 7634 8387 8914 1613 8591 1690 2381 305 2395 2085 8844 424 9671 1058 8914 1613 8844 424 63 2852 147 1148 7502 5454 6908 4386 6908...
result:
ok answer = 1
Test #7:
score: -100
Wrong Answer
time: 2ms
memory: 3740kb
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 90608 87653 84773 93522 90608 87653 98020 74176 90608 87653 98457 88434 9204 2816 17439 857 90608 87653 96182 95797 98742 10618 99229 57468 2472 46829 80752 9209 2472 46829 50244 62708 59944 148 52006 1692 1522 99921 48815 98534 888 90680 649 91204 888 90680 48815 98534 649 91204 710 39900 84773...
result:
wrong output format Unexpected end of file - int32 expected