QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#193564#7521. Find the Gapucup-team963#WA 75ms3816kbC++144.2kb2023-09-30 17:28:292023-09-30 17:28:29

Judging History

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

  • [2023-09-30 17:28:29]
  • 评测
  • 测评结果:WA
  • 用时:75ms
  • 内存:3816kb
  • [2023-09-30 17:28:29]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define debug(a) cout<<#a<<a<<endl;
#define int long long
#define io_speed_up ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef unsigned long long u64;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define double long double
const int N=55;
const double eps=1e-9;
int sgn(double x){
    return x<-eps?-1:x>eps;
}
struct point3{
    double x,y,z;
}e[N];
point3 xmu(point3 u,point3 v){
    point3 ret;
    ret.x=u.y*v.z-v.y*u.z;
    ret.y=u.z*v.x-u.x*v.z;
    ret.z=u.x*v.y-u.y*v.x;
    return ret;
}
double dmu(point3 u,point3 v){
    return u.x*v.x+u.y*v.y+u.z*v.z;
}
point3 subt(point3 u,point3 v){
    point3 ret;
    ret.x=u.x-v.x;
    ret.y=u.y-v.y;
    ret.z=u.z-v.z;
    return ret;
}
double vlen(point3 p){
    return sqrt(p.x*p.x+p.y*p.y+p.z*p.z);
}
point3 pvec(point3 s1,point3 s2,point3 s3){
    return xmu(subt(s1,s2),subt(s2,s3));
}
int dot_inline(point3 p1,point3 p2,point3 p3){
    return vlen(xmu(subt(p1,p2),subt(p2,p3)))<eps;
}
int dot_onplane(point3 a,point3 b,point3 c,point3 d){
    return sgn(dmu(pvec(a,b,c),subt(d,a)));
}
int parallel(point3 u1,point3 v1,point3 u2,point3 v2){
    return vlen(xmu(subt(u1,v1),subt(u2,v2)))<eps;
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        double x,y,z;
        cin>>x>>y>>z;
        e[i].x=x;
        e[i].y=y;
        e[i].z=z;
    }
    double ans=0x3f3f3f3f3f3f*1.0;
    
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            for(int k=j+1;k<=n;k++){
                if(dot_inline(e[i],e[j],e[k])) continue;
                else{   
                    double inf=0x3f3f3f3f3f3f*1.0;
                    double maxx=0;
                    double dis=maxx-inf;
                    //cout<<i<<" "<<j<<" "<<k<<endl;
                    point3 ret=pvec(e[i],e[j],e[k]);
                    for(int p=1;p<=n;p++){
                        double temp=dmu(ret,e[p])/vlen(ret);
                        if(sgn(dmu(ret,e[p]))==0) temp=0;
                        inf=min(inf,temp);
                        maxx=max(maxx,temp);
                        dis=maxx-inf;
                    }
                    // cout<<i<<" "<<j<<" "<<k<<" "<<endl;
                    // cout<<dis<<endl;
                    ans=min(ans,dis);
                }
            }
        }
    }
    for(int u1=1;u1<=n;u1++){
        for(int v1=u1+1;v1<=n;v1++){
            for(int u2=1;u2!=u1&&u2!=v1&&u2<=n;u2++){
                for(int v2=u2+1;v2!=u1&&v2!=v1&&v2<=n;v2++){
                    int flag=parallel(e[u1],e[v1],e[u2],e[v2]);
                    int flag2=dot_onplane(e[u1],e[u2],e[v1],e[v2]);
                    if(flag==1||flag2==0) continue;
                    else{
                        double inf=0x3f3f3f3f3f3f*1.0;
                        double maxx=0;
                        double dis=maxx-inf;
                        point3 u3=subt(e[u1],subt(e[v2],e[u2]));
                        point3 ret=pvec(e[u1],e[v1],u3);
                        for(int p=1;p<=n;p++){
                            double temp=dmu(ret,e[p])/vlen(ret);
                            if(sgn(dmu(ret,e[p]))==0) temp=0;
                            inf=min(inf,temp);
                            maxx=max(maxx,temp);
                            dis=maxx-inf;
                        }
                        // cout<<u1<<" "<<v1<<" "<<u2<<" "<<v2<<" "<<"sige"<<endl;
                        // cout<<dis<<endl;
                        ans=min(ans,dis);
                    }
                }
            }
        }
    }
    if(sgn(ans-0x3f3f3f3f3f3f*1.0)==0) {
        double temp=0;
        cout<<fixed<<setprecision(15)<<temp<<endl;
        return ;
    }
    cout<<fixed<<setprecision(15)<<ans<<endl;
}
signed main(){
    io_speed_up;
    solve();
    return 0;
}
/*
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
5
1 1 1
1 2 1
1 1 2
1 2 2
2 1 1
8
2 2 2
12 12 2
2 7 3
12 8 3
7 2 3
7 12 3 
2 12 4 
12 2 4

5
1 4 5
2 7 9
6 1 1
4 3 2
10 10 10
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3728kb

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.000000000000000

result:

ok found '1.000000000', expected '1.000000000', error '0.000000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3688kb

input:

5
1 1 1
1 2 1
1 1 2
1 2 2
2 1 1

output:

0.707106781186548

result:

ok found '0.707106781', expected '0.707106781', error '0.000000000'

Test #3:

score: 0
Accepted
time: 5ms
memory: 3816kb

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.000000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #4:

score: 0
Accepted
time: 5ms
memory: 3644kb

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.000000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #5:

score: 0
Accepted
time: 11ms
memory: 3704kb

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.000000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #6:

score: 0
Accepted
time: 9ms
memory: 3632kb

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.000000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #7:

score: -100
Wrong Answer
time: 75ms
memory: 3760kb

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:

9345.824681487764606

result:

wrong answer 1st numbers differ - expected: '9341.5658962', found: '9345.8246815', error = '0.0004559'