QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#193185 | #7521. Find the Gap | ucup-team918# | WA | 107ms | 58848kb | C++17 | 4.7kb | 2023-09-30 16:33:40 | 2023-09-30 16:33:57 |
Judging History
answer
//Was yea ra,rra yea ra synk sphilar yor en me exec hymme METAFALICA waath!
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
using namespace std;
#define rg register
#define ll long long
#define ull unsigned ll
#define lowbit(x) (x&(-x))
#define djq 998244353
const double eps=1e-12;
const short sint=0x3f3f;
const int inf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;
const double alpha=0.73;
const double PI=acos(-1);
inline void file(){
freopen("ball.in","r",stdin);
freopen("ball.out","w",stdout);
}
char buf[1<<21],*p1=buf,*p2=buf;
inline int getc(){
return p1==p2&&(p2=(p1=buf)+fread(buf,1,(1<<20)+5,stdin),p1==p2)?EOF:*p1++;
}
//#define getc getchar
inline ll read(){
rg ll ret=0,f=0;char ch=getc();
while(!isdigit(ch)){if(ch==EOF)exit(0);if(ch=='-')f=1;ch=getc();}
while(isdigit(ch)){ret=ret*10+ch-48;ch=getc();}
return f?-ret:ret;
}
inline int rdstr(char* s){
char ch=getc(); int len(0);
while(ch<33||ch>126) ch=getc();
while(ch>=33&&ch<=126) (*s++)=ch,++len,ch=getc();
return len;
}
#define ep emplace
#define epb emplace_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define it iterator
#define mkp make_pair
#define naive return 0*puts("Yes")
#define angry return 0*puts("No")
#define fls fflush(stdout)
#define rep(i,a) for(rg int i=1;i<=a;++i)
#define per(i,a) for(rg int i=a;i;--i)
#define rep0(i,a) for(rg int i=0;i<=a;++i)
#define per0(i,a) for(rg int i=a;~i;--i)
#define szf sizeof
typedef vector<int> vec;
typedef pair<int,int> pii;
struct point{ int x,y; point(int x=0,int y=0):x(x),y(y) {} inline bool operator<(const point& T)const{ return x^T.x?x<T.x:y<T.y; }; };
inline int ksm(int base,int p){int ret=1;while(p){if(p&1)ret=1ll*ret*base%djq;base=1ll*base*base%djq,p>>=1;}return ret;}
inline void pls(int& x,const int k){ x=(x+k>=djq?x+k-djq:x+k); }
inline int add(const int a,const int b){ return a+b>=djq?a+b-djq:a+b; }
inline void sub(int& x,const int k){ x=(x-k<0?x-k+djq:x-k); }
inline int inc(const int a,const int b){ return a<b?a-b+djq:a-b; }
inline void ckmn(int& x,const int k){ x=(k<x?k:x); }
inline void ckmx(int& x,const int k){ x=(k>x?k:x); }
inline void ckmn(ll& x,const ll k){ x=(k<x?k:x); }
inline void ckmx(ll& x,const ll k){ x=(k>x?k:x); }
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define Vector Point
inline int dcmp(double a){return a<-eps?-1:(a>eps?1:0); }
inline double Abs(double a){return a*dcmp(a);}
double reps(){return (1.*(rnd()%98)/97-.5)*eps;}
struct Point{
double x,y,z;
void shake(){x+=reps(),y+=reps(),z+=reps();}
Point(double x=0,double y=0,double z=0):x(x),y(y),z(z) {}
}p[55];
inline Vector operator+(Vector a,Vector b){ return Vector(a.x+b.x,a.y+b.y,a.z+b.z); }
inline Vector operator-(Vector a,Vector b){ return Vector(a.x-b.x,a.y-b.y,a.z-b.z); }
inline Vector operator*(Vector a,double b){ return Vector(a.x*b,a.y*b,a.z*b); }
inline Vector operator/(Vector a,double b){ return Vector(a.x/b,a.y/b,a.z/b); }
inline double Dot(Point a,Point b){ return a.x*b.x+a.y*b.y+a.z*b.z; }
inline double Len(Point a){ return sqrt(Dot(a,a)); }
inline Point Cro(Point a,Point b){ return Point(a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x); }
struct face{
int v[3];
inline Point area(){ return Cro(p[v[1]]-p[v[0]],p[v[2]]-p[v[0]]); }
inline bool check(int x){ return Dot(p[x]-p[v[0]],area())>0?1:0; }
};
int n;
bool flag,vis[2005][2005];
vector<face> cur;
double ans;
inline void solve(){
cur.clear();
cur.push_back((face){1,2,3});
cur.push_back((face){3,2,1});
for(rg int i=4;i<=n;++i){
vector<face> tmp;
for(rg int j=0;j<cur.size();++j){
face now=cur[j];
int checker=now.check(i);
if(!checker) tmp.epb(now);
for(rg int k=0;k<3;++k){
vis[now.v[k]][now.v[(k+1)%3]]=checker;
}
}
for(rg int j=0;j<cur.size();++j){
for(rg int k=0;k<3;++k){
int now=cur[j].v[k],nex=cur[j].v[(k+1)%3];
if(vis[now][nex]!=vis[nex][now]&&vis[now][nex]){
tmp.push_back((face){now,nex,i});
}
}
}
cur=tmp;
}
}
signed main(){
//file();
n=read();
rep(i,n) p[i].x=read(),p[i].y=read(),p[i].z=read(),p[i].shake();
solve(); double ans=1e9;
for(rg int i=0;i<cur.size();++i){
Point a=p[cur[i].v[0]],b=p[cur[i].v[1]],c=p[cur[i].v[2]];
//printf("(%.3lf,%.3lf,%.3lf) (%.3lf,%.3lf,%.3lf) (%.3lf,%.3lf,%.3lf)\n",a.x,a.y,a.z,b.x,b.y,b.z,c.x,c.y,c.z);
double ar=Len(Cro(b-a,c-a)),mx(0);
rep(i,n){
double nw=Dot(p[i]-a,Cro(b-a,c-a))/Len(Cro(b-a,c-a));
mx=max(mx,fabs(nw));
}
ans=min(ans,mx);
}
printf("%.11lf\n",ans);
return 0;
}
/*
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5964kb
input:
8 1 1 1 1 1 2 1 2 1 1 2 2 2 1 1 2 1 2 2 2 1 2 2 2
output:
1.00000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5908kb
input:
5 1 1 1 1 2 1 1 1 2 1 2 2 2 1 1
output:
0.70710678119
result:
ok found '0.707106781', expected '0.707106781', error '0.000000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 6120kb
input:
50 973 1799 4431 1036 1888 4509 1099 1977 4587 1162 2066 4665 1225 2155 4743 1288 2244 4821 1351 2333 4899 1414 2422 4977 1540 2600 5133 1603 2689 5211 1666 2778 5289 1729 2867 5367 1792 2956 5445 1855 3045 5523 1918 3134 5601 1981 3223 5679 2044 3312 5757 2107 3401 5835 2170 3490 5913 2296 3668 606...
output:
0.00000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #4:
score: 0
Accepted
time: 107ms
memory: 58848kb
input:
50 4532 3245 1339 4624 3260 1345 4716 3275 1351 4808 3290 1357 4900 3305 1363 5084 3335 1375 5176 3350 1381 5268 3365 1387 5360 3380 1393 5452 3395 1399 5544 3410 1405 5728 3440 1417 5820 3455 1423 5912 3470 1429 6096 3500 1441 6188 3515 1447 6280 3530 1453 6372 3545 1459 6464 3560 1465 6556 3575 14...
output:
0.00000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 6004kb
input:
50 1 70 7443 1 138 5063 2 109 5971 3 23 8874 3 152 4359 4 59 7507 5 50 7715 5 73 6910 7 25 8376 7 103 5646 8 3 9039 9 83 6132 9 142 4067 10 124 4590 11 140 3923 12 168 2836 13 46 6999 13 84 5669 13 189 1994 13 229 594 15 171 2410 16 94 4998 20 38 6530 20 125 3485 21 78 5023 22 210 296 23 117 3444 25...
output:
0.00000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 6076kb
input:
50 1 95 5991 3 22 9019 25 103 5199 25 141 3603 38 103 4952 39 139 3421 59 6 8627 60 48 6844 66 33 7360 107 88 4271 109 188 33 112 177 438 114 107 3340 122 77 4448 123 169 565 127 1 7545 142 161 540 143 70 4343 146 153 800 156 129 1618 162 63 4276 162 150 622 166 93 2940 173 78 3437 180 143 574 189 1...
output:
0.00000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #7:
score: -100
Wrong Answer
time: 1ms
memory: 7924kb
input:
50 14 3658 1218 17 32 7984 741 1906 5773 755 8668 1019 834 2386 4591 1306 3866 7044 2304 2895 120 2450 8613 7374 2595 1919 2119 2610 9866 9419 2694 2845 2941 2838 2702 7608 2883 4143 4049 3082 4800 3611 3338 6703 9039 3424 2035 1863 3471 2672 5858 4339 1330 2029 4720 6970 4719 4853 387 5866 5415 975...
output:
9414.05796416416
result:
wrong answer 1st numbers differ - expected: '9341.5658962', found: '9414.0579642', error = '0.0077602'