QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#44520#142. 平面最近点对QingyuCompile Error//C++231.7kb2022-08-18 19:21:392022-08-18 19:21:42

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-18 19:21:42]
  • 评测
  • [2022-08-18 19:21:39]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i ++)
#define per(i, r, l) for(int i = (r); i >= (l); i --)
#define trv(i, u, v) for(int i = head[u], v = e[i].to; i; v = e[i = e[i].nxt].to)
#define fi first
#define se second
#define all(s) s.begin(), s.end()
#define sz(s) (int)(s.size())
#define lb(s) ((s) & -(s))
#define pb push_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
mt19937_64 hua(time(0));
template<typename T> inline bool chkmx(T &x, T y) {return x < y ? x = y, 1 : 0;}
template<typename T> inline bool chkmn(T &x, T y) {return y < x ? x = y, 1 : 0;}
const int maxn = 2e6;
int n;
struct Node {
	ll x, y;
}a[maxn + 5];
struct cmp {
	bool operator () (const Node &x, const Node &y) const {
		return x.y == y.y ? x.x < y.x : x.y < y.y;
	}
};
set<Node, cmp> s;
__int128 sqr(__int128 x) {return x * x;}
__int128 dis(Node x, Node y) {
	return sqr(x.x - y.x) + sqr(x.y - y.y);
}
int main() {
//	freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	rep(i, 1, n) cin >> a[i].x >> a[i].y;
	sort(a + 1, a + n + 1, [&] (Node x, Node y) {return x.x < y.x;});
	ll ans = dis(a[1], a[2]);
	s.insert(a[1]), s.insert(a[2]); 
	int p = 1;
	rep(i, 3, n) {
		while(sqr(a[i].x - a[p].x) >= ans) s.erase(a[p]), p ++;
		auto it = s.lower_bound(a[i]);
		for(auto p = it; p != s.end() && sqr(p -> y - a[i].y) < ans; p ++) {
			chkmn(ans, dis(*p, a[i]));
		}
		if(it != s.begin()) for(auto p = prev(it); sqr(p -> y - a[i].y) < ans; p --) {
			chkmn(ans, dis(*p, a[i]));
			if(p == s.begin()) break;
		}
		s.insert(a[i]);
	}
	cout << fixed << setprecision(20) << sqrtl(ans) << '\n';
	return 0;
}

Details

answer.code: In function ‘int main()’:
answer.code:47:30: error: no matching function for call to ‘chkmn(ll&, __int128)’
   47 |                         chkmn(ans, dis(*p, a[i]));
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~
answer.code:17:34: note: candidate: ‘template<class T> bool chkmn(T&, T)’
   17 | template<typename T> inline bool chkmn(T &x, T y) {return y < x ? x = y, 1 : 0;}
      |                                  ^~~~~
answer.code:17:34: note:   template argument deduction/substitution failed:
answer.code:47:30: note:   deduced conflicting types for parameter ‘T’ (‘long long int’ and ‘__int128’)
   47 |                         chkmn(ans, dis(*p, a[i]));
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~
answer.code:50:30: error: no matching function for call to ‘chkmn(ll&, __int128)’
   50 |                         chkmn(ans, dis(*p, a[i]));
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~
answer.code:17:34: note: candidate: ‘template<class T> bool chkmn(T&, T)’
   17 | template<typename T> inline bool chkmn(T &x, T y) {return y < x ? x = y, 1 : 0;}
      |                                  ^~~~~
answer.code:17:34: note:   template argument deduction/substitution failed:
answer.code:50:30: note:   deduced conflicting types for parameter ‘T’ (‘long long int’ and ‘__int128’)
   50 |                         chkmn(ans, dis(*p, a[i]));
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~