QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#212891#7521. Find the Gapucup-team061WA 13ms3944kbC++203.2kb2023-10-13 22:12:372023-10-13 22:12:38

Judging History

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

  • [2023-10-13 22:12:38]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:3944kb
  • [2023-10-13 22:12:37]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int ll
#define fr first
#define se second
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define all(x) x.begin(),x.end()
#define For(i,a,b) for(int i = a; i <= b; ++i)
#define Rep(i,a,b) for(int i = a; i >= b; --i)
using namespace std;
typedef pair<int,int> pii;
#ifdef OVAL
const int N = 2e3+10;
#else
const int N = 2e5+10;
#endif
#define double long double
#define eps 1e-10
struct point3{double x,y,z;};
struct line3{point3 a,b;};
struct plane3{point3 a,b,c;};
typedef point3 P;
point3 xmult(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;
}
//计算 dot product product product product U . V
double dmult(point3 u,point3 v){
	return u.x*v.x+u.y*v.y+u.z*v.z;
}
//矢量差 U - V
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;
}
//取法向量
point3 pvec(plane3 s){
	return xmult(subt(s.a,s.b),subt(s.b,s.c));
}
point3 pvec(point3 s1,point3 s2,point3 s3){
	return xmult(subt(s1,s2),subt(s2,s3));
}
point3 intersection(point3 l1,point3 l2,point3 s1,point3 s2,point3 s3){
	point3 ret=pvec(s1,s2,s3);
	double t=(ret.x*(s1.x-l1.x)+ret.y*(s1.y-l1.y)+ret.z*(s1.z-l1.z))/
	(ret.x*(l2.x-l1.x)+ret.y*(l2.y-l1.y)+ret.z*(l2.z-l1.z));
	ret.x=l1.x+(l2.x-l1.x)*t;
	ret.y=l1.y+(l2.y-l1.y)*t;
	ret.z=l1.z+(l2.z-l1.z)*t;
	return ret;
}
double vlen(point3 p){
	return sqrt(p.x*p.x+p.y*p.y+p.z*p.z);
}
P unit(P p){
	double len = vlen(p);
	return {p.x/len, p.y/len, p.z/len};
}
int dots_inline(point3 p1,point3 p2,point3 p3){
	return vlen(xmult(subt(p1,p2),subt(p2,p3)))<eps;
}
//直线平行
int parallel(line3 u,line3 v){
return vlen(xmult(subt(u.a,u.b),subt(v.a,v.b)))<eps;
}
int parallel(point3 u1,point3 u2,point3 v1,point3 v2){
return vlen(xmult(subt(u1,u2),subt(v1,v2)))<eps;
}
//平面平行
int parallel(plane3 u,plane3 v){
	return vlen(xmult(pvec(u),pvec(v)))<eps;
}
int parallel(point3 u1,point3 u2,point3 u3,point3 v1,point3 v2,point3 v3){
	return vlen(xmult(pvec(u1,u2,u3),pvec(v1,v2,v3)))<eps;
}

double ptoplane(point3 p,plane3 s){
	return fabs(dmult(pvec(s),subt(p,s.a)))/vlen(pvec(s));
}
double ptoplane(point3 p,point3 s1,point3 s2,point3 s3){
	return fabs(dmult(pvec(s1,s2,s3),subt(p,s1)))/vlen(pvec(s1,s2,s3));
}
int n;
P ps[N];
void solve()
{
	cin >> n;
	For(i,1,n){
		cin >> ps[i].x >> ps[i].y >> ps[i].z;
	}
	if(n<=3){
		cout << "0\n";return;
	}
	double ans = 1e99;
	For(i,1,n)For(j,i+1,n){
		P vec1 = subt(ps[i], ps[j]);
		For(k,1,n)For(l,k+1,n){
			P vec2 = subt(ps[k], ps[l]);
			P fa = xmult(vec1, vec2);
			if(fabsl(vlen(fa)) < eps)continue;
			fa = unit(fa);
			double mx = -1e99, mn = 1e99;
			For(w,1,n){
				double ds = dmult(fa, ps[w]);
				mx = max(mx, ds);
				mn = min(mn, ds);
			}
			ans = min(ans, mx-mn);
		}
	}
	cout << ans << '\n';
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	int tt = 1;
	cout << fixed << setprecision(12);
	// cin >> tt;
	For(tc,1,tt){
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

result:

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

Test #2:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

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

output:

0.707106781187

result:

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

Test #3:

score: -100
Wrong Answer
time: 13ms
memory: 3744kb

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:

999999999999999967336168804116691273849533185806555472917961779471295845921727862608739868455469056.000000000000

result:

wrong answer 1st numbers differ - expected: '0.0000000', found: '999999999999999967336168804116691273849533185806555472917961779471295845921727862608739868455469056.0000000', error = '999999999999999967336168804116691273849533185806555472917961779471295845921727862608739868455469056.0000000'