QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#576396 | #7521. Find the Gap | ucup-team2818 | RE | 0ms | 0kb | C++14 | 2.6kb | 2024-09-19 20:14:06 | 2024-09-19 20:14:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9;
struct Point
{
ld x, y, z;
Point(ld X = 0, ld Y = 0, ld Z = 0) { x = X, y = Y, z = Z; }
Point operator - (const Point &b)const { return Point(x - b.x, y - b.y, z - b.z); }
Point operator * (const ld &b)const { return Point(x * b, y * b, z * b); }
bool operator == (const Point &b)const { return x == b.x && y == b.y && z == b.z; }
}p[55], q[55];
bool coline(Point d, Point e) { return d.x * e.y == d.y * e.x && d.x * e.z == d.z * e.x; }
ld dot(Point a, Point b) { return a.x * b.x + a.y * b.y + a.z * b.z; }
Point cross(Point a, Point b)
{
Point c;
c.x = a.y * b.z - a.z * b.y;
c.y = a.z * b.x - a.x * b.z;
c.z = a.x * b.y - a.y * b.x;
return c;
}
int st[55], top; vector<int> vc;
ld len(Point p) { return sqrt(dot(p, p)); }
bool chk(Point a, Point b, Point c, Point P, bool t) { if (!t) return dot(P, cross(a - b, b - c)) <= 0; return dot(P, cross(a - b, b - c)) >= 0; }
int main()
{
ios::sync_with_stdio(0), cin.tie(0);
int n; cin >> n;
for (int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y >> p[i].z;
bool Fl = true; for (int i = 3; i <= n; i++) Fl &= coline(p[1] - p[2], p[1] - p[i]);
if (Fl) { return cout << "0", 0; }
ld ans = 1e9;
for (int a = 1; a <= n; a++)
for (int b = a + 1; b <= n; b++)
{
Point P = p[a] - p[b];
for (int c = 1; c <= n; c++) q[c] = p[c] - P * (dot(p[c], P) / dot(P, P));
sort(q + 1, q + n + 1, [&](Point i, Point j) { if (i.x != j.x) return i.x < j.x; if (i.y != j.y) return i.y < j.y; return i.z < j.z; });
st[top = 1] = 1, st[top = 2] = 2; vc.clear();
for (int i = 3; i <= n; i++)
{
while (top > 1 && chk(q[st[top - 1]], q[st[top]], q[i], P, 0)) top--;
st[++top] = i;
}
for (int i = 1; i < top; i++) vc.emplace_back(st[i]);
st[top = 1] = 1, st[top = 2] = 2;
for (int i = 3; i <= n; i++)
{
while (top > 1 && chk(q[st[top - 1]], q[st[top]], q[i], P, 1)) top--;
st[++top] = i;
}
for (int i = top; i >= 1; i--) vc.emplace_back(st[i]);
for (int i = 0; i + 1 < vc.size(); i++)
{
int c = vc[i], d = vc[i + 1]; ld res = 0.0;
for (int j = 1; j <= n; j++) assert(dot(P, cross(q[c] - q[d], q[j] - q[d])) >= 0);
for (int j = 1; j <= n; j++) res = max(res, len(cross(q[c] - q[d], q[j] - q[d])) / len(q[c] - q[d]));
ans = min(ans, res);
}
}
cout.precision(15);
cout << ans;
return 0;
}
详细
Test #1:
score: 0
Runtime Error
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