QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#576396#7521. Find the Gapucup-team2818RE 0ms0kbC++142.6kb2024-09-19 20:14:062024-09-19 20:14:07

Judging History

This is the latest submission verdict.

  • [2024-09-19 20:14:07]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2024-09-19 20:14:06]
  • Submitted

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

output:


result: