QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#194789#7521. Find the Gapucup-team484#WA 0ms3728kbC++172.1kb2023-09-30 22:28:132023-09-30 22:28:14

Judging History

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

  • [2023-09-30 22:28:14]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3728kb
  • [2023-09-30 22:28:13]
  • 提交

answer

#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define st first
#define nd second
using namespace std;
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;

template<class T> struct Point3D {
  typedef Point3D P;
  typedef const P& R;
  T x, y, z;
  explicit Point3D(T x=0, T y=0, T z=0) : x(x), y(y), z(z) {}
  P operator+(R p) const { return P(x+p.x, y+p.y, z+p.z); }
  P operator-(R p) const { return P(x-p.x, y-p.y, z-p.z); }
  T dot(R p) const { return x*p.x + y*p.y + z*p.z; }
  P cross(R p) const {
    return P(y*p.z - z*p.y, z*p.x - x*p.z, x*p.y - y*p.x);
  }
};

typedef Point3D<ll> P3;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n; cin >> n;
	if (n <= 3) {
		cout << "0.0\n";
		return 0;
	}
	vector<P3> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i].x >> a[i].y >> a[i].z;
	ld ans = 1e18;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			for (int k = i + 1; k < n; k++) {
				if (k == i || k == j) continue;
				for (int l = k + 1; l < n; l++) {
					if (l == i || l == j) continue;
					P3 dir = (a[j] - a[i]).cross(a[k] - a[l]);
					int x1 = 0, x2 = 0;
					int y1 = 0, y2 = 0;
					for (int m = 0; m < n; m++) {
						ll v1 = dir.dot(a[m] - a[i]);
						ll v2 = dir.dot(a[m] - a[l]);
						x1 += v1 > 0; y1 += v1 < 0;
						x2 += v2 > 0; y2 += v2 < 0;
					}
					if (x1 > 0 && y1 > 0 || x2 > 0 && y2 > 0)
						continue;
					ld len = sqrtl(dir.x * dir.x + dir.y * dir.y + dir.z * dir.z);
					ans = min(ans, (ld)abs(dir.dot(a[i] - a[k])) / len);
				}
			}
			for (int k = j + 1; k < n; k++) {
				P3 dir = (a[j] - a[i]).cross(a[k] - a[i]);
				int x = 0, y = 0;
				ld cur = 0, len = sqrtl(dir.x * dir.x + dir.y * dir.y + dir.z * dir.z);
				for (int l = 0; l < n; l++) {
					ll val = dir.dot(a[l] - a[i]);
					x += val < 0;
					y += val > 0;
					cur = max(cur, (ld)abs(val) / len);
				}
				if (x > 0 && y > 0)
					continue;
				ans = min(ans, cur);
			}
		}
	}
	cout << fixed << setprecision(15) << ans << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3728kb

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:

0.000000000000000

result:

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