QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#92337#142. 平面最近点对Yansuan_HCl#Compile Error//C++141.4kb2023-03-30 15:59:422023-03-30 15:59:46

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-30 15:59:46]
  • 评测
  • [2023-03-30 15:59:42]
  • 提交

answer

#include <bits/stdc++.h>
#define ms(x, v) memset(x, v, sizeof(x))
#define il __attribute__((always_inline))
#define U(i,l,r) for(int i=l,END##i=r; i<=END##i; ++i)
#define D(i,l,r) for(int i=l,END##i=r; i>=END##i; --i)
using namespace std;
using ll = __int128;
const ll INF = ll(0x3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f);

#define GC c=getchar()
#define IC isdigit(c)
void rd(auto &s) { s = 0; char GC;
	for (; !IC; GC);
	for (; IC; GC) s = s * 10 + c - 48;
} void rd(auto &s, auto &...t) { rd(s); rd(t...); }

const int N = 2000006;
struct Pt { ll x, y; } pt[N];
bool operator < (const Pt &l, const Pt &r) {
	return l.x == r.x ? l.y < r.y : l.x < r.x; }
bool cmp(const Pt &l, const Pt &r) { return l.y < r.y; }
ll Q(ll x) { return x * x; }

int n;
ll solve(int l, int r) {
	if (l == r) return INF;
	int mid((l + r) >> 1);
	ll mX = pt[mid].x;
	ll d = min(solve(l, mid), solve(mid + 1, r));
	inplace_merge(pt + l, pt + mid + 1, pt + r + 1, cmp);
	
	int p = l, q = l;
	U (i, l, r) {
		while (q < r && Q(pt[q + 1].y - pt[i].y) <= d)
			++q;
		while (p < q && Q(pt[i].y - pt[p].y) > d)
			++p;
		if (Q(pt[i].x - mX) > d) continue;
		U (j, p, q) if (i != j)
			d = min(d, Q(pt[i].x - pt[j].x) + Q(pt[i].y - pt[j].y));
	}
	return d;
}

int main() {
	rd(n);
	U (i, 1, n) rd(pt[i].x, pt[i].y);
	
	sort(pt + 1, pt + n + 1);
	ll ans = solve(1, n);
	printf("%.8lf", sqrt(__float128(ans)));
}

Details

answer.code:8:19: warning: integer constant is too large for its type
    8 | const ll INF = ll(0x3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f3f);
      |                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:12:9: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts-ts’
   12 | void rd(auto &s) { s = 0; char GC;
      |         ^~~~
answer.code:15:11: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts-ts’
   15 | } void rd(auto &s, auto &...t) { rd(s); rd(t...); }
      |           ^~~~
answer.code:15:20: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts-ts’
   15 | } void rd(auto &s, auto &...t) { rd(s); rd(t...); }
      |                    ^~~~
answer.code: In function ‘int main()’:
answer.code:51:29: error: call of overloaded ‘sqrt(__float128)’ is ambiguous
   51 |         printf("%.8lf", sqrt(__float128(ans)));
      |                         ~~~~^~~~~~~~~~~~~~~~~
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)
      |   ^~~~