QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#193133 | #7521. Find the Gap | ucup-team963# | WA | 2ms | 3800kb | C++14 | 3.8kb | 2023-09-30 16:26:04 | 2023-09-30 16:26:05 |
Judging History
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;
const int N=55;
const double eps=1e-8;
int sgn(double x){
return x<-eps?-1:x>eps;
}
struct point3{
double x,y,z;
}e[N];
struct line3{
point3 a,b;
};
struct plane3{
point3 a,b,c;
};
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;
}
//tongce
int same_side(point3 p1,point3 p2,point3 s1,point3 s2,point3 s3){
return dmu(pvec(s1,s2,s3),subt(p1,s1))*dmu(pvec(s1,s2,s3),subt(p2,s1))>eps;
}
int opp_side(point3 p1,point3 p2,point3 s1,point3 s2,point3 s3){
return dmu(pvec(s1,s2,s3),subt(p1,s1))*dmu(pvec(s1,s2,s3),subt(p2,s1))<-eps;
}
double ptoplane(point3 p,point3 s1,point3 s2,point3 s3){
return fabs(dmu(pvec(s1,s2,s3),subt(p,s1)))/vlen(pvec(s1,s2,s3));
}
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;
//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);
inf=min(inf,temp);
maxx=max(maxx,temp);
}
ans=min(ans,maxx-inf);
}
}
}
}
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!=u2&&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;
point3 u3=subt(e[u2],subt(e[v1],e[v2]));
point3 ret=pvec(e[u1],e[v1],u3);
for(int p=1;p<=n;p++){
double temp=dmu(ret,e[p])/vlen(ret);
inf=min(inf,temp);
maxx=max(maxx,temp);
}
ans=min(ans,maxx-inf);
}
}
}
}
}
cout<<fixed<<setprecision(15)<<ans<<endl;
}
signed main(){
io_speed_up;
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3800kb
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: 0ms
memory: 3716kb
input:
5 1 1 1 1 2 1 1 1 2 1 2 2 2 1 1
output:
0.707106781186547
result:
ok found '0.707106781', expected '0.707106781', error '0.000000000'
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 3584kb
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:
69540876599103.000000000000000
result:
wrong answer 1st numbers differ - expected: '0.0000000', found: '69540876599103.0000000', error = '69540876599103.0000000'