QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#113504#6639. Disk TreeHegdahlWA 5ms4108kbC++206.0kb2023-06-18 09:24:552023-06-18 09:24:58

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-18 09:24:58]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:4108kb
  • [2023-06-18 09:24:55]
  • 提交

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 <= 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: 3524kb

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

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

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

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

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: 3ms
memory: 3772kb

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: 5ms
memory: 4108kb

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 98180 22402
90608 87653 17439 857
90608 87653 59944 148
59944 148 15549 49146
27055 9398 831 69461
74594 17647 15549 49146
70298 94974 65247 29347
7841 81086 49332 30334
908 79893 66345 83699
31276 94106 9726 31739
17694 68695 98180 22402
31276 94106 49332 30334
59314 96287 27055 939...

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