不知道怎么去找数据卡我这个代码,有没有大佬卡下我这个用精度狗过去的代码,感觉应该是有数据卡的。
#include <bits/stdc++.h>
// #pragma GCC optimize(2)
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#define isPbdsFile
#ifdef isPbdsFile
#include <bits/extc++.h>
#else
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/rope>
#endif
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
#define gc() getchar()
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
typedef pair<int, int> PI;
const int maxnum = 2e6 + 5;
const int mof = 0x3f3f3f3f;
const i64 mod = 1e9 + 7;
const i64 basic = 233;
const i64 MOF = 0x3f3f3f3f3f3f3f3f;
#define hash1 unordered_map
#define hash2 gp_hash_table
#define hash3 cc_hash_table
namespace IO {
template <typename T>
void read(T& x)
{
x = 0;
T sign = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')sign = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
x *= sign;
}
template <typename T, typename... U>
void read(T& x, U&... y)
{
read(x);
read(y...);
}
template <typename T>
void write(T x)
{
if (typeid(x) == typeid(char))return;
if (x < 0)x = -x, putchar('-');
if (x > 9)write(x / 10);
putchar(x % 10 ^ 48);
}
template <typename C, typename T, typename... U>
void write(C c, T x, U... y)
{
write(x), putchar(c);
write(c, y...);
}
}
using namespace IO;
struct Hash{
static uint64_t splitmix64(uint64_t x)
{
x += 0x9e3779b97f4a7c15;
x = (x ^ x >> 30) * 0xbf58476d1ce4e5b9;
x = (x ^ x >> 27) * 0x94d049bb133111eb;
return x ^ x >> 31;
}
static size_t get(const uint64_t x)
{
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
template <typename T>
size_t operator()(T x) const
{
return get(std::hash<T>()(x));
}
template <typename F, typename S>
size_t operator()(pair<F, S> p) const
{
return get(std::hash<F>()(p.first)) ^ std::hash<S>()(p.second);
}
};
void solve() {
int n;
read(n);
struct q{
double x, y;
bool operator < (const q &t) const {
if (x != t.x) return x < t.x;
return y < t.y;
}
};
vector<int> temp(n + 1);
vector<q> a(n + 1);
for (int i = 1; i <= n; i++) {
double x, y;
scanf("%lf %lf", &x, &y);
a[i] = {x, y};
}
stable_sort(a.begin() + 1, a.end());
auto dist = [&] (double x_1, double y_1, double x_2, double y_2) {
double ans1 = x_1 - x_2;
double ans2 = y_1 - y_2;
return sqrt(ans1 * ans1 + ans2 * ans2);
};
function<double(int, int)> cdq = [&] (int L, int R) {
double d = 2e9;
if (L == R) return d;
int pos = 0;
int mid = L + R >> 1;
d = min(cdq(L, mid), cdq(mid + 1, R));
for (int i = L; i <= R; i++) {
if (fabs(a[mid].x - a[i].x) < d) {
temp[++pos] = i;
}
}
stable_sort(temp.begin() + 1, temp.begin() + pos + 1, [&] (const int &k1, const int &k2) {
return a[k1].y < a[k2].y;
});
for (int i = 1; i <= pos; i++) {
for (int j = i + 1; j <= pos && a[temp[j]].y - a[temp[i]].y < d; j++) {
d = min(d, dist(a[temp[i]].x, a[temp[i]].y, a[temp[j]].x, a[temp[j]].y));
}
}
return d;
};
double ans = powl(cdq(1, n), 2);
i64 res;
if (ans - i64(ans) >= 0.5) res = (i64)ans + 1ll;
else res = (i64)ans;
printf("%lld\n", res);
}
int main() {
int _ = 1;
// read(_);
while (_--) solve();
return 0;
}