QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#151968#142. 平面最近点对fstqwqCompile Error//C++201.7kb2023-08-27 15:38:432023-08-27 15:38:47

Judging History

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

  • [2023-08-27 15:38:47]
  • 评测
  • [2023-08-27 15:38:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef __int128 LLL;
inline LL read () {
	int ch = getchar(); LL a = 0;
	while (ch < '0') ch = getchar();
	while (ch >= '0') a = a * 10 + ch - '0', ch = getchar();
	return a;
}

struct point {
	LL x, y;
};
bool cmpx (const point &a, const point &b) { return a.x < b.x;}
bool cmpy (const point &a, const point &b) { return a.y < b.y;}

LLL pow2 (LLL x) {
	return x * x;
}
LLL dis (const point &a, const point &b) {
	return pow2(a.x - b.x) + pow2(a.y - b.y);
}

int n;
vector <point> a;


void merge (int l, int mid, int r) {
	int i = l, j = mid;
	vector <point> tmp;
	while (i < mid || j < r) {
		if (i < mid && (j == r || cmpy(a[i], a[j]))) tmp.push_back(a[i++]);
		else tmp.push_back(a[j++]);
	}
	for (auto &i : tmp) {
		a[l++] = i;
	}
	assert (l == r);
}

LLL solve (int l, int r) {
	if (l + 1 >= r) return LLL(1e30);
	int mid = (l + r) / 2;
	LL mx = a[mid].x;
	LLL ret = min(solve(l, mid), solve(mid, r));
	merge(l, mid, r);
	for (int i = l + 1; i < r; i++) {
		assert (a[i - 1].y <= a[i].y);
	}
	vector <point> strip;
	for (int i = l; i < r; i++) {
		if (pow2(a[i].x - mx) < ret) {
			strip.push_back(a[i]);
		}
	}
	for (int i = 0; i < (int) strip.size(); i++) {
		for (int j = i + 1; j < (int) strip.size(); j++) {
			if (pow2(strip[i].y - strip[j].y) >= ret) break;
			ret = min(ret, dis(strip[i], strip[j]));
		}
	}
	return ret;
}

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		LL x, y;
		x = read(); y = read();
		a.push_back({x, y});
	}
	sort(a.begin(), a.end(), cmpx);
	cout << fixed << setprecision(9) << sqrt (solve(0, n)) << endl;
}

Details

answer.code: In function ‘int main()’:
answer.code:74:50: error: call of overloaded ‘sqrt(LLL)’ is ambiguous
   74 |         cout << fixed << setprecision(9) << sqrt (solve(0, n)) << endl;
      |                                             ~~~~~^~~~~~~~~~~~~
In file included from /usr/include/features.h:461,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/os_defines.h:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/c++config.h:571,
                 from /usr/include/c++/11/cassert:43,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:33,
                 from answer.code:1:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:143:1: note: candidate: ‘double sqrt(double)’
  143 | __MATHCALL (sqrt,, (_Mdouble_ __x));
      | ^~~~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:1:
/usr/include/c++/11/cmath:467:3: note: candidate: ‘constexpr long double std::sqrt(long double)’
  467 |   sqrt(long double __x)
      |   ^~~~
/usr/include/c++/11/cmath:463:3: note: candidate: ‘constexpr float std::sqrt(float)’
  463 |   sqrt(float __x)
      |   ^~~~