QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#91469#142. 平面最近点对Minion#0 0ms0kbC++232.0kb2023-03-28 22:04:102023-03-28 22:04:42

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-28 22:04:42]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-03-28 22:04:10]
  • 提交

answer

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<random>
#include<ctime>
#define fo(i,x,y) for(int i = x;i <= y;++i)
#define fd(i,x,y) for(int i = x;i >= y;--i)
#define _is 1048576 * 60
#define gc() ib[++bi]
#define ll long long
#define D double
#define N 2000010
#define mp 4000003
using namespace std;
char ib[_is];int bi = -1;
ll rd()
{
	int x = 0,sig = 0;char ch = gc();
	while(ch < 48 || ch > 57) ch = gc();
	while(ch >= 48 && ch <= 57) x = x * 10 + ch - 48,ch = gc();
	return x;
}
int n,p[N];
ll a[N],b[N];
inline D sqr(D x) {return x * x;}
inline D dis(int x,int y) {return sqrtl(sqr(a[x] - a[y]) + sqr(b[x] - b[y]));}
struct hs
{
	D s;
	ll bx[N],by[N],id[N],nxt[N],lst[mp],tot;
	hs() {}
	int H(ll x,ll y) {return (100000ll * x + y) % mp;}
	int tst(int ID)
	{
		if(s == 0) return 0;
		ll fx = a[ID] / s,fy = b[ID] / s,h = H(fx,fy);
		bool bz = 0;
		fo(i,-1,1) fo(j,-1,1)
		{
			ll nx = fx + i,ny = fy + j;
			if(nx < 0 || ny < 0) continue;
			int h = H(nx,ny);
			for(int k = lst[h];k;k = nxt[k]) if(dis(id[k],ID) < s) return 1;
		}
		return 0;
	}
	void ins(int ID)
	{
		if(s == 0) return;
		ll fx = a[ID] / s,fy = b[ID] / s,h = H(fx,fy);
		bool bz = 0;
		fo(i,-1,1)
		{
			ll nx = fx + i;
			if(nx >= 0) fo(j,-1,1)
			{
				ll ny = fy + j;
				if(ny < 0) continue;
				int h = H(nx,ny);
				for(int k = lst[h];k;k = nxt[k]) if(dis(id[k],ID) < s) s = dis(id[k],ID),bz = 1;
			}
		}
		if(s == 0) return;
		bx[++tot] = fx,by[tot] = fy,id[tot] = ID,nxt[tot] = lst[h],lst[h] = tot;
		if(bz)
		{
			fo(i,1,tot) lst[H(bx[i],by[i])] = 0;
			fo(i,1,tot)
			{
				bx[i] = a[id[i]] / s,by[i] = b[id[i]] / s;
				int h = H(bx[i],by[i]);
				nxt[i] = lst[h],lst[h] = i;
			}
		}
	}
}h;
int main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	fread(ib,1,_is,stdin);
	n = rd();
	fo(i,1,n) a[i] = rd(),b[i] = rd(),p[i] = i;
	mt19937_64 gen(time(0));
	fo(i,2,n)
	{
		int x = gen() % i + 1;
		swap(p[x],p[i]);
	}
	h.s = dis(1,2);
	fo(i,1,n) h.ins(p[i]);
	printf("%.10lf\n",h.s);
}

详细

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

input:

2933
19320 28055
2053 27470
14635 1378
27582 9822
28729 107
22351 3093
17670 379
23901 4686
27182 12261
19443 8467
24208 20283
10763 10584
25953 28380
28290 27394
19572 14769
4024 12401
23295 3267
26949 176
13416 4517
23856 15413
26260 18957
18275 24409
999 3873
28202 14686
25446 2822
24009 8949
114...

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%