QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#91469 | #142. 平面最近点对 | Minion# | 0 | 0ms | 0kb | C++23 | 2.0kb | 2023-03-28 22:04:10 | 2023-03-28 22:04:42 |
Judging History
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%