QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#210167#7521. Find the GapUSP_USP_USP#WA 25ms3760kbC++202.8kb2023-10-11 05:02:512023-10-11 05:02:51

Judging History

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

  • [2023-10-11 05:02:51]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:3760kb
  • [2023-10-11 05:02:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ld = long double;
#define double ld
#define all(v) (v).begin(), (v).end()
#define pb push_back

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

const double EPS = 1e-8;
bool zero(double x) { return abs(x) < EPS; }

struct point {
	double x, y, z;
	point(): x(0), y(0), z(0) {}
	point(double _x, double _y, double _z): x(_x), y(_y), z(_z) {}
	bool operator==(const point rhs) const {
		return zero(x-rhs.x) && zero(y-rhs.y) && zero(z-rhs.z);
	}
	point operator+(const point rhs) const { return point(x+rhs.x, y+rhs.y, z+rhs.z); }
	point operator-(const point rhs) const { return point(x-rhs.x, y-rhs.y, z-rhs.z); }
	point operator*(const double c) const { return point(c*x, c*y, c*z); }
	point operator/(const double c) const { return point(x/c, y/c, z/c); }
	point operator^(const point rhs) const { return point(y*rhs.z-z*rhs.y, z*rhs.x-x*rhs.z, x*rhs.y - y*rhs.x); }
	double operator*(const point rhs) const { return x * rhs.x + y*rhs.y + z*rhs.z; }
};

struct plane {
	array<point, 3> p;
	array<double, 4> eq;

	plane() {}
	plane(point _p, point _q, point _r): p({_p, _q, _r}) {
		point dir = (p[1] - p[0]) ^ (p[2] - p[0]);
		dir = dir / sqrt((dir * dir));
		eq = {dir.x, dir.y, dir.z, dir * (p[0]) * (-1) };
	};
};

double sdist(point p, plane P) {
	return P.eq[0] * p.x + P.eq[1] * p.y + P.eq[2] * p.z + P.eq[3];
}

double dist(point p, plane P) {
	return abs(P.eq[0] * p.x + P.eq[1] * p.y + P.eq[2] * p.z + P.eq[3]);
}

const double INF = 1e10;

void solve() {
	int n; cin >> n;
	vector<point> pts(n);
	double ans = numeric_limits<int>::max();
	for(auto &[x, y, z]: pts) cin >> x >> y >> z;
	for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) for(int k=j+1;k<n;k++) {
		if( ((pts[j] - pts[i]) ^ (pts[k] - pts[i])) == point() ) 
			continue;
		plane P(pts[i], pts[j], pts[k]);
		double mn = INF, mx = -INF;
		for(point p: pts) {
			double d = sdist(p, P);
			mn = min(d, mn);
			mx = max(d, mx);
		}
		assert(!zero(mx - mn));
		ans = min(ans, mx - mn);
	}
	for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) for(int k=0;k<n;k++) for(int l=k+1;l<n;l++) {
		array<int, 4> v = {i, j, k, l};
		sort(all(v));
		if(v[0] == v[1] || v[1] == v[2] || v[2] == v[3]) continue;
		plane P;
		point dir = (pts[j] - pts[i]) ^ (pts[l] - pts[k]);
		if(dir == point()) continue;
		P.eq[0] = dir.x; P.eq[1] = dir.y; P.eq[2] = dir.z; P.eq[3] = 0;
		double mn = INF, mx = -INF;
		for(point p: pts) {
			double d = sdist(p, P);
			mn = min(d, mn);
			mx = max(d, mx);
		}
		assert(!zero(mx - mn));
		ans = min(ans, mx - mn);
	}

	cout << ans << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(10);
	solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3760kb

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: 1ms
memory: 3708kb

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: -100
Wrong Answer
time: 25ms
memory: 3716kb

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:

2147483647.0000000000

result:

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