QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#44518 | #142. 平面最近点对 | Qingyu | Compile Error | / | / | C++20 | 1.7kb | 2022-08-18 19:20:16 | 2022-08-18 19:20:17 |
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:20:17]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2022-08-18 19:20:16]
- 提交
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 () (Node x, Node y) {
return x.y == y.y ? x.x < y.x : x.y < y.y;
}
};
set<Node, cmp> s;
ll sqr(ll x) {return x * x;}
ll 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;
}
详细
In file included from /usr/include/c++/11/map:60, from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:81, from answer.code:1: /usr/include/c++/11/bits/stl_tree.h: In instantiation of ‘static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type) [with _Key = Node; _Val = Node; _KeyOfValue = std::_Identity<Node>; _Compare = cmp; _Alloc = std::allocator<Node>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node<Node>*]’: /usr/include/c++/11/bits/stl_tree.h:2069:47: required from ‘std::pair<std::_Rb_tree_node_base*, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_unique_pos(const key_type&) [with _Key = Node; _Val = Node; _KeyOfValue = std::_Identity<Node>; _Compare = cmp; _Alloc = std::allocator<Node>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = Node]’ /usr/include/c++/11/bits/stl_tree.h:2122:4: required from ‘std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = const Node&; _Key = Node; _Val = Node; _KeyOfValue = std::_Identity<Node>; _Compare = cmp; _Alloc = std::allocator<Node>]’ /usr/include/c++/11/bits/stl_set.h:512:25: required from ‘std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = Node; _Compare = cmp; _Alloc = std::allocator<Node>; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<Node, Node, std::_Identity<Node>, cmp, std::allocator<Node> >::const_iterator; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other = std::allocator<Node>; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key> = __gnu_cxx::__alloc_traits<std::allocator<Node>, Node>::rebind<Node>; typename _Alloc::value_type = Node; std::set<_Key, _Compare, _Alloc>::value_type = Node]’ answer.code:41:10: required from here /usr/include/c++/11/bits/stl_tree.h:770:15: error: static assertion failed: comparison object must be invocable as const 770 | is_invocable_v<const _Compare&, const _Key&, const _Key&>, | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /usr/include/c++/11/bits/stl_tree.h:770:15: note: ‘std::is_invocable_v<const cmp&, const Node&, const Node&>’ evaluates to false