用的是加强版的代码过的,感觉数据还可以再弄强一点,有没有大佬卡下我的数据
查看原帖
用的是加强版的代码过的,感觉数据还可以再弄强一点,有没有大佬卡下我的数据
895827
grape_king楼主2024/3/19 15:31

不知道怎么去找数据卡我这个代码,有没有大佬卡下我这个用精度狗过去的代码,感觉应该是有数据卡的。

#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;
}
2024/3/19 15:31
加载中...