QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226843#7521. Find the GapJayintWA 17ms3944kbC++145.0kb2023-10-26 17:11:542023-10-26 17:11:54

Judging History

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

  • [2023-10-26 17:11:54]
  • 评测
  • 测评结果:WA
  • 用时:17ms
  • 内存:3944kb
  • [2023-10-26 17:11:54]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const double pi = acos(-1.0);//高精度圆周率
const double eps = 1e-8;//偏差值
const int maxp = 1010;//点的数量
#define db long double
//判断是否等于零,返回0为等于零,返回-1为小于,1为大于
int sgn(double x) {
	if (fabs(x) < eps)return 0;
	else return x < 0 ? -1 : 1;
}

//判断是否相等,返回0为相等,返回-1为小于,1为大于
int dcmp(double x, double y) {
	if (fabs(x - y) < eps)return 0;
	else return x < y ? -1 : 1;
}

//三维几何
struct Point3 {
	double x, y, z;
	Point3() {}
	Point3(double x, double y, double z) : x(x), y(y), z(z) {}
	Point3 operator+(Point3 B) { return Point3(x + B.x, y + B.y, z + B.z); }
	Point3 operator-(Point3 B) { return Point3(x - B.x, y - B.y, z + B.z); }
	Point3 operator*(double k) { return Point3(x * k, y * k, z * k); }//放大k倍
	Point3 operator/(double k) { return Point3(x / k, y / k, z / k); }//缩小k倍
	bool operator==(Point3 B) { return sgn(x - B.x) == 0 && sgn(y - B.y) == 0 && sgn(z - B.z) == 0; }
};

typedef Point3 Vector3;
//两点距离
double Distance(Point3 A, Point3 B) { return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y) + (A.z - B.z) * (A.z - B.z));}

struct Line3 {
	Point3 p1, p2;
	Line3() {}
	//根据端点确定直线
	Line3(Point3 p1, Point3 p2) : p1(p1), p2(p2) {}
};

typedef Line3 Segment3;
//向量点积
double Dot(Vector3 A, Vector3 B) { return A.x * B.x + A.y * B.y + A.z * B.z;}

//向量长度
double vector_length(Vector3 A) { return sqrt(Dot(A, A));}

//向量长度平方
double vector_length_square(Vector3 A) { return Dot(A, A);}

//向量夹角
double Angle(Vector3 A, Vector3 B) {
	return acos(Dot(A, B) / vector_length(A) / vector_length(B));
}

//向量叉积;大于0,B在A逆时针方向;等于0,A、B重合
Vector3 Cross(Vector3 A, Vector3 B) { return Point3 (A.y * B.z - A.z * B.y, A.z * B.x - A.x * B.z, A.x * B.y - A.y * B.x);}

//三点构成平行四边形面积(A为公共点)
double Area2(Point3 A, Point3 B, Point3 C) {
	return vector_length(Cross(B - A, C - A));
}

//判断p是否在三角形ABC内,可以用Area2来计算;如果点p在三角形内部,那么用电p对三角形ABC进行刨分,形成的3个三角形的面积应和直接计算ABC的面积相等

// dcmp(Area2(p, A, B) + Area2(p, B, C) + Area2(p, C, A), Area2(A, B, C)) == 0;

//点在直线上
bool Point_line_relation(Point3 p, Segment3 v) {
	return sgn(vector_length(Cross(v.p1 - p, v.p2 - p))) == 0 && sgn(Dot(v.p1 - p, v.p2 - p)) == 0;
}

//点到直线的距离
double Dis_point_line(Point3 p, Line3 v) {
	return vector_length(Cross(v.p2 - v.p1, p - v.p1) / Distance(v.p1, v.p2));
}

//点在直线上的投影
Point3 Point_line_proj(Point3 p, Line3 v) {
	double k = Dot(v.p2 - v.p1, p - v.p1) / vector_length_square(v.p2 - v.p1);
	return v.p1 + (v.p2 - v.p1) * k;
}

//点到线段的距离
double Dis_point_seg(Point3 p, Segment3 v) {
	if (sgn(Dot(p - v.p1, v.p2 - v.p1)) < 0 || sgn(Dot(p - v.p2, v.p1 - v.p2)) < 0) //点的投影不在线段上
		return min(Distance(p, v.p1), Distance(p, v.p2));
	return Dis_point_line(p, v); //点的投影在线段上
}

//三维 : 平面
struct Plane {
	Point3 p1, p2, p3;
	Plane() {}
	Plane(Point3 p1, Point3 p2, Point3 p3) : p1(p1) , p2(p2), p3(p3) {}
};

//平面法向量
Point3 pvec(Point3 A, Point3 B, Point3 C) { return Cross(B - A, C - A); }
Point3 pvec(Plane f) { return Cross(f.p2 - f.p1, f.p3 - f.p1); }

//四点共平面
bool Point_on_plane(Point3 A, Point3 B, Point3 C, Point3 D) {
	return sgn(Dot(pvec(A, B, C), D - A)) == 0;
}

//两平面平行
int parallel(Plane f1, Plane f2) {
	return vector_length(Cross(pvec(f1), pvec(f2))) < eps;
}

//两平面垂直
int vertical(Plane f1, Plane f2) {
	return sgn(Dot(pvec(f1), pvec(f2))) == 0;
}

//直线与平面的交点p,返回值是交点的个数
int Line_cross_plane(Line3 u, Plane f, Point3 &p) {
	Point3 v = pvec(f); //平面的法向量
	double x = Dot(v, u.p2 - f.p1);
	double y = Dot(v, u.p1 - f.p1);
	double d = x - y;
	if (sgn(x) == 0 && sgn(y) == 0) return -1; //v在f上
	if (sgn(d) == 0) return 0; //v与f平行
	p = ((u.p1 * x) - (u.p2 * y)) / d; //v与f相交
	return 1;
}

//四面体有向体积X6
double volume4(Point3 A, Point3 B, Point3 C, Point3 D) {
	return Dot(Cross(B - A, C - A), D - A);
}

Point3 p[55];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		p[i] = Point3(x, y, z);
	}
	db ans = 1e18;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				if (i == j || i == k || j == k) continue;
				Vector3 a = p[j] - p[i], b = p[k] - p[i];
				Vector3 v1 = Cross(a, b);
				db maxn = -1e18;
				db minn = 1e18;
				for (int ii = 1; ii <= n; ii++) {
					Vector3 v2 = p[ii] - p[i];
					db k = Dot(v1, v2) / vector_length(v1);
					maxn = max(maxn, k);
					minn = min(minn, k);
				}
				ans = min(ans, maxn - minn);
			}
		}
	}
	printf("%.10Lf\n", ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3848kb

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

result:

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

Test #2:

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

input:

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

output:

0.7071067812

result:

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

Test #3:

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

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

result:

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

Test #4:

score: 0
Accepted
time: 17ms
memory: 3692kb

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

result:

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

Test #5:

score: -100
Wrong Answer
time: 16ms
memory: 3736kb

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:

1.3338496800

result:

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