QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#126415#142. 平面最近点对c20231020#0 2ms3840kbC++207.8kb2023-07-18 14:50:502023-07-18 14:50:53

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-18 14:50:53]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:3840kb
  • [2023-07-18 14:50:50]
  • 提交

answer

/*
膜拜传奇特级宗师 Afterglow 大神儿
今天在 florr 首页称您为大夏尊贵的大名儿
一股敬佩之情油生然而
您在 florr 为国争光,扬我大夏威名
向您献上最真挚的膜拜!!!
膜拜传奇特级宗师 Afterglow 大神儿,今,一,您,扬。向!
膜拜传奇特级宗师 Afterglow 大神儿,今,一,您,扬。向!
膜拜传奇特级宗师 Afterglow 大神儿,今,一,您,扬。向!
*/
/*
          _____                    _____                     _____                    _____
         /\    \                  /\    \                   /\    \                  /\    \
        /  \    \                /  \    \                 /  \____\                /  \    \
        \   \    \              /    \    \               /   /    /                \   \    \
         \   \    \            /      \    \             /   /    /                  \   \    \
          \   \    \          /   /\   \    \           /   /____/                    \   \    \
           \   \    \        /   /  \   \    \         /    |    |                     \   \    \
            \   \    \      /   /    \   \    \       /     |    |                      \   \    \
             \   \    \    /   /    / \   \    \     /      |    |                       \   \    \
              \   \    \  /   /    /   \   \    \   /       |____|__ _____                \   \    \
_______________\   \____\/   /____/     \   \    \ /   /|            \    \ _______________\   \____\
\                  /    /\   \    \      \   \    \\  / |    _________\____\\                  /    /
 \    ____________/____/  \   \    \      \   \____\\/__|   |    |           \    ____________/____/
  \   \    \               \   \    \     |   |    |    |   |    |            \   \    \
   \   \    \               \   \    \    |   |    |    |   |    |             \   \    \
    \   \    \               \   \    \   |   |____|    |   |    |              \   \    \
     \   \    \               \   \    \  /   /    /    \   |    |               \   \    \
      \   \    \               \   \    \/   /    /      \  |    |                \   \    \
       \   \____\               \   \___/   /    /        \ |    |                 \   \____\
        \  /    /                \         /    /          \|    |                  \  /    /
         \/____/                  \_______/____/            \____|                   \/____/
*/
#define poj
//#define zcz
#ifdef poj
//C++
#include<iomanip>
#include<iostream>
//C
#include<cassert>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
//STL
#include<algorithm>
#include<bitset>
#include<functional>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<vector>
//C++11
#if __cplusplus>=201103L
#include<chrono>
#include<random>
#include<unordered_set>
#include<unordered_map>
#endif
#else
#include<bits/stdc++.h>
#endif
using namespace std;
#ifdef zcz
class fastin{
	private:
#ifdef poj
	static const int MAXBF=1<<20;
#else
	const int MAXBF=1<<27;
#endif
	FILE *inf;
	char *inbuf,*inst,*ined;
	inline char _getchar(){
		if(inst==ined)inst=inbuf,ined=inbuf+fread(inbuf,1,MAXBF,inf);
		return inst==ined?EOF:*inst++;
	}
	public:
	fastin(FILE*_inf=stdin){
		inbuf=new char[MAXBF],inf=_inf,inst=inbuf,ined=inbuf;
	}
	~fastin(){delete inbuf;}
	template<typename Int> fastin&operator>>(Int &n){
		static char c;
		Int t=1;
		while((c=_getchar())<'0'||c>'9')if(c=='-')t=-1;
		n=(c^48);
		while((c=_getchar())>='0'&&c<='9')n=n*10+(c^48);
		n*=t;
		return *this;
	}
	fastin&operator>>(char&c){
		while((c=_getchar())<'!'||c>'~');
		return *this;
	}
	fastin&operator>>(char*s){
		int t=0;
		static char c;
		while((c=_getchar())==' '||c=='\n');
		s[t++]=c;
		while((c=_getchar())>='!'&&c<='~')s[t++]=c;
		s[t]='\0';
		return *this;
	}
}fi;
class fastout{
	private:
#ifdef poj
	static const int MAXBF=1<<20;
#else
	const int MAXBF=1<<27;
#endif
	FILE *ouf;
	char *oubuf,*oust,*oued;
	inline void _flush(){fwrite(oubuf,1,oued-oust,ouf);oued=oust;}
	inline void _putchar(char c){
		if(oued==oust+MAXBF)_flush(),oued=oubuf;
		*oued++=c;
		#ifdef local
		_flush();
		#endif
	}
	public:
	fastout(FILE*_ouf=stdout){
		oubuf=new char[MAXBF],ouf=_ouf,oust=oubuf,oued=oubuf;
	}
	~fastout(){_flush();delete oubuf;}
	template<typename Int> fastout&operator<<(Int n){
		if(n<0)_putchar('-'),n=-n;
		static char S[20];
		int t=0;
		do{S[t++]='0'+n%10,n/=10;}while(n);
		for(int i=0;i<t;++i)_putchar(S[t-i-1]);
		return *this;
	}
	fastout&operator<<(char c){_putchar(c);return *this;}
	fastout&operator<<(char*s){
		for(int i=0;s[i];++i)_putchar(s[i]);
		return *this;
	}
	fastout&operator<<(const char*s){
		for(int i=0;s[i];++i)_putchar(s[i]);
		return *this;
	}
}fo;
#define cin fi
#define cout fo
#else
#define czc ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#endif
#define mod7 1000000007
#define mod9 998244353
#define ll long long
#define isinf 0x3f3f3f3f
#define ilinf 0x7fffffff
#define lsinf 0x3f3f3f3f3f3f3f3f
#define llinf 0x7fffffffffffffff
#define pii pair<int,int>
#define fr first
#define sc second
#define next ___
#define pb push_back
#define N 2000010
#define M 5000010
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b,c) for(int i=(a);i<=(b);i+=c)
#define Per(i,a,b,c) for(int i=(a);i>=(b);i-=c)
#define Gra(i) for(int i=h[x];i;i=next[i])
typedef int arr[N];
typedef int arm[M];
typedef ll arl[N];
typedef ll alm[M];
typedef double ard[N];
typedef double adm[M];
namespace modint{
	template<typename Int,Int mod>
	struct modint{
		Int v;
		modint(){v=0;}
		modint(Int a){v=a;}
		bool operator==(modint a){return v==a.v;}
		bool operator!=(modint a){return v!=a.v;}
		bool operator<(modint a){return v<a.v;}
		bool operator>(modint a){return v>a.v;}
		bool operator<=(modint a){return v<=a.v;}
		bool operator>=(modint a){return v>=a.v;}
		bool operator==(Int a){return v==a;}
		bool operator!=(Int a){return v!=a;}
		bool operator<(Int a){return v<a;}
		bool operator>(Int a){return v>a;}
		bool operator<=(Int a){return v<=a;}
		bool operator>=(Int a){return v>=a;}
		modint operator+(modint a){return v>mod-a.v?v-mod+a.v:v+a.v;}
		modint operator-(modint a){return v>a.v?v-a.v:v+mod-a.v;}
		modint operator*(modint a){return v*a.v%mod;}
		modint operator+=(modint a){*this=*this+a;return *this;}
		modint operator-=(modint a){*this=*this-a;return *this;}
		modint operator*=(modint a){*this=*this*a;return *this;}
		modint qpow(modint a,Int b){
			modint r(1);
			for(;b;b>>=1,a*=a)if(b&1)r*=a;
			return r;
		}
		modint operator/(modint a){return qpow(a,mod-2)*v;}
		modint operator/=(modint a){*this=*this/a;return *this;}
		modint&operator++(){*this=*this+1;return *this;}
		modint&operator--(){*this=*this-1;return *this;}
		const modint operator++(int){modint r=*this;++*this;return r;}
		const modint operator--(int){modint r=*this;--*this;return r;}
		#ifdef cout
		friend fastout&operator<<(fastout&out,modint n){out<<n.v;return out;}
		#else
		friend ostream&operator<<(ostream&out,modint n){out<<n.v;return out;}
		#endif
	};
	typedef modint<long long,1000000007> int7;
	typedef modint<long long,998244353> int9;
}
using namespace modint;
int n;
double ans=1e20;
struct G{
	double x,y,a,b;
}a[N];
void solve(){
	cin>>n;
	double p=sin(1.114514),q=cos(1.114514);
	For(i,1,n){
		cin>>a[i].x>>a[i].y;
		a[i].a=a[i].x*q-a[i].y*p;
		a[i].b=a[i].x*p+a[i].y*q;
	}
	sort(a+1,a+1+n,[](G x,G y){
		return x.a*x.b<y.a*y.b;
	});
	For(i,1,n){
		For(j,i+1,n){
			if(a[j].x-a[i].x>ans)break;
			ans=min(ans,sqrt((a[j].x-a[i].x)*(a[j].x-a[i].x)+(a[j].y-a[i].y)*(a[j].y-a[i].y)));
		}
	}
	cout<<fixed<<setprecision(20)<<ans;
	return;
}
int main(){
	#ifndef zcz
	czc;
	#endif
	int t=1;
	while(t--)solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 15
Accepted
time: 2ms
memory: 3792kb

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:

2.82842712474619029095

result:

ok found '2.8284271', expected '2.8284271', error '0.0000000'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3760kb

input:

2912
721 22031
501 17261
11583 2570
25091 26662
7053 8645
13085 13755
15427 10176
10602 28715
16277 17856
9356 11466
5758 16745
4367 27948
15523 3209
27447 13908
24316 27667
11649 8344
9848 2897
219 21503
22524 11664
5725 1460
24127 12567
25935 14858
8457 13415
16347 12044
28163 753
28967 22202
2418...

output:

8.60232526704262667749

result:

ok found '8.6023253', expected '8.6023253', error '0.0000000'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3840kb

input:

2919
2259 8882
27694 23328
12744 20731
7265 21050
9456 6920
13055 18791
28400 8457
16815 27147
17978 11787
8903 7696
17316 10505
28428 15732
15370 9751
23862 25477
5316 5647
24987 27499
11625 15403
27782 4138
9728 5740
18123 13962
2177 7071
27078 7038
4083 2679
28762 5376
16196 6309
2708 25797
23383...

output:

14.14213562373095101066

result:

ok found '14.1421356', expected '14.1421356', error '0.0000000'

Test #4:

score: -15
Wrong Answer
time: 2ms
memory: 3732kb

input:

2998
25897 23111
13024 10321
15964 26479
17278 5912
13799 21852
20180 4213
27326 12582
1533 11852
16882 2495
528 13201
21465 18041
540 4999
28233 3336
9986 1089
6821 20255
3089 17725
4583 22110
3588 8106
25230 22362
18344 2991
26627 13592
29199 19
23076 17065
20627 9037
639 2945
26311 15104
4108 118...

output:

10.63014581273464997935

result:

wrong answer 1st numbers differ - expected: '8.4852814', found: '10.6301458', error = '0.2527747'

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%