QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#113505#6639. Disk TreeHegdahlWA 5ms4096kbC++206.0kb2023-06-18 09:26:432023-06-18 09:26:47

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:26:47]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:4096kb
  • [2023-06-18 09:26:43]
  • 提交

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