QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#226843 | #7521. Find the Gap | Jayint | WA | 17ms | 3944kb | C++14 | 5.0kb | 2023-10-26 17:11:54 | 2023-10-26 17:11:54 |
Judging History
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'