QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#126414 | #142. 平面最近点对 | c20231020# | 0 | 2ms | 3848kb | C++20 | 7.9kb | 2023-07-18 14:50:09 | 2023-07-18 14:50:10 |
Judging History
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,min(i+60,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: 3848kb
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: 3820kb
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: 3816kb
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: 3728kb
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%