QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#168787#6639. Disk Treeucup-team1209Compile Error//C++202.0kb2023-09-08 22:00:012023-09-08 22:00:02

Judging History

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

  • [2023-09-08 22:00:02]
  • 评测
  • [2023-09-08 22:00:01]
  • 提交

answer

#include<bits/stdc++.h>
using std::cin;
using std::cout;
const int N = 200005;


using db = double;
using cp = std::complex<db>;
const db pi = std::acos(-1);

std::mt19937 gen(time(0) + (size_t) new char);
int n;
cp a[N], b[N];
int r[N], id0[N], id1[N];
int pos[N];
struct edge { int u, v; db w; };
std::vector<edge> e;
int anc[N];
db dist(int x, int y) { return abs(a[x] - a[y]) - r[x] - r[y]; }
struct pr {
	db w; int id;
} bit[N];
int find(int x) {
	return anc[x] == x ? x : anc[x] = find(anc[x]);
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	cin >> n;
	for(int i = 0;i < n;++i) {
		int x, y; cin >> x >> y >> r[i];
		a[i] = cp(x, y);
		id0[i] = i;
		id1[i] = i;
		anc[i] = i;
	}
	for(db arg : {0, 0.25, 0.5, 0.75}) {
		cp r = std::polar(1., arg * pi * 2);
		for(int i = 0;i < n;++i) b[i] = a[i] * r;
		std::sort(id0, id0 + n, [](int x, int y) { return b[x].real() < b[y].real(); });
		std::sort(id1, id1 + n, [](int x, int y) { return b[x].imag() < b[y].imag(); });
		for(int j = 0;j < n;++j) {
			pos[id1[j]] = j + 1;
		}
		for(int i = 1;i <= n;++i) {
			bit[i] = {5e9, -1};
		}
		for(int i = n - 1;i >= 0;--i) {
			int x = id0[i];

			int id = -1;
			db dx = 5e9;

			for(int i = pos[x];i <= n;i += i & -i) {
				int t = bit[i].id;
				if(t != -1) {
					db dd = dist(t, x);
					if(id == -1) {
						id = t;
						dx = dd;
					} else {
						if(dd < dx) {
							dx = dd;
							id = t;
						}
					}
				}
			}

			pr z = { b[x].real() + b[x].imag() - ::r[x], x};
			for(int i = pos[x];i;i &= i - 1) {
				if(z.w < bit[i].w) bit[i] = z;
			}
			if(id >= 0) {
				e.push_back({x, id, dx});
			}
		}
	}
	sort(e.begin(), e.end(), [](edge x, edge y) { return x.w < y.w; });
	cout << "YES" << '\n';
	for(auto [u, v, w] : e) {
		if(find(u) != find(v)) {
			cout << (int) a[u].real() << ' ' << (int) a[u].imag() << ' ';
			cout << (int) a[v].real() << ' ' << (int) a[v].imag() << '\n';
			anc[find(u)] = find(v);
		}
	}
}

Details

answer.code: In function ‘int main()’:
answer.code:36:41: error: unable to deduce ‘std::initializer_list<auto>&&’ from ‘{0, 2.5e-1, 5.0e-1, 7.5e-1}’
   36 |         for(db arg : {0, 0.25, 0.5, 0.75}) {
      |                                         ^
answer.code:36:41: note:   deduced conflicting types for parameter ‘auto’ (‘int’ and ‘double’)