QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#193413 | #7521. Find the Gap | ucup-team1516# | WA | 2ms | 3904kb | C++20 | 4.9kb | 2023-09-30 17:06:37 | 2023-09-30 17:06:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define ti3 tuple<int,int,int>
#define int128 __int128_t
#define pii128 pair<int128,int128>
const int inf = 1 << 30;
const ll linf = 1e18;
const ll mod = 1e9 + 7;
const db EPS = 1e-10;
const db pi = acos(-1);
template<class T> bool chmin(T& x, T y){
if(x > y) {
x = y;
return true;
} else return false;
}
template<class T> bool chmax(T& x, T y){
if(x < y) {
x = y;
return true;
} else return false;
}
// overload macro
#define CAT( A, B ) A ## B
#define SELECT( NAME, NUM ) CAT( NAME, NUM )
#define GET_COUNT( _1, _2, _3, _4, _5, _6 /* ad nauseam */, COUNT, ... ) COUNT
#define VA_SIZE( ... ) GET_COUNT( __VA_ARGS__, 6, 5, 4, 3, 2, 1 )
#define VA_SELECT( NAME, ... ) SELECT( NAME, VA_SIZE(__VA_ARGS__) )(__VA_ARGS__)
// rep(overload)
#define rep( ... ) VA_SELECT(rep, __VA_ARGS__)
#define rep2(i, n) for (int i = 0; i < int(n); i++)
#define rep3(i, a, b) for (int i = a; i < int(b); i++)
#define rep4(i, a, b, c) for (int i = a; i < int(b); i += c)
// repll(overload)
#define repll( ... ) VA_SELECT(repll, __VA_ARGS__)
#define repll2(i, n) for (ll i = 0; i < ll(n); i++)
#define repll3(i, a, b) for (ll i = a; i < ll(b); i++)
#define repll4(i, a, b, c) for (ll i = a; i < ll(b); i += c)
// rrep(overload)
#define rrep( ... ) VA_SELECT(rrep, __VA_ARGS__)
#define rrep2(i, n) for (int i = n - 1; i >= 0; i--)
#define rrep3(i, a, b) for (int i = b - 1; i >= a; i--)
#define rrep4(i, a, b, c) for (int i = b - 1; i >= a; i -= c)
// rrepll(overload)
#define rrepll( ... ) VA_SELECT(rrepll, __VA_ARGS__)
#define rrepll2(i, n) for (ll i = n - 1; i >= 0ll; i--)
#define rrepll3(i, a, b) for (ll i = b - 1; i >= ll(a); i--)
#define rrepll4(i, a, b, c) for (ll i = b - 1; i >= ll(a); i -= c)
// for_earh
#define fore(e, v) for (auto&& e : v)
// vector
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
int n;
int x[60], y[60], z[60];
long double ans = inf;
struct vec {
ll x, y, z;
vec () {}
vec (ll a, ll b, ll c) : x(a), y(b), z(c) {}
bool operator == (vec v) const {
return x == v.x && y == v.y && z == v.z;
}
};
vec make_vec(int i, int j) {
vec v;
v.x = x[j] - x[i];
v.y = y[j] - y[i];
v.z = z[j] - z[i];
ll g = gcd(v.x, v.y);
g = gcd(g, v.z);
if (v.x < 0) g *= -1;
if (v.x == 0 && v.y < 0) g *= -1;
if (v.x == 0 && v.y == 0 && v.z < 0) g *= -1;
v.x /= g, v.y /= g, v.z /= g;
return v;
}
vec product(vec v1, vec v2) {
ll g = gcd(v1.y * v2.z - v1.z * v2.y, gcd(v1.z * v2.x - v1.x * v2.z, v1.x * v2.y - v1.y * v2.x));
return vec{(v1.y * v2.z - v1.z * v2.y) / g, (v1.z * v2.x - v1.x * v2.z) / g, (v1.x * v2.y - v1.y * v2.x) / g};
}
ll dot(vec v1, vec v2) {
return v1.x * v2.x + v1.y * v2.y + v1.z * v2.z;
}
long double len(vec v) {
cout << v.x << ' ' << v.y << ' ' << v.z << endl;
return sqrtl(v.x * v.x + v.y * v.y + v.z * v.z);
}
long double judge(int a, int b, int c, int d) {
vec v[2] = {make_vec(a, b), make_vec(c, d)};
if (v[0] == v[1]) return inf;
auto h = product(v[0], v[1]);
rep (i, 2) {
int side[2] = {};
rep (j, n) {
int s = (i ? c : a);
ll d = dot(h, vec{x[j] - x[s], y[j] - y[s], z[j] - z[s]});
if (d < 0) side[0]++;
if (d > 0) side[1]++;
}
if (side[0] && side[1]) return inf;
}
long double ret = 0;
rep (i, n) {
chmax(ret, abs((long double)dot(h, vec{x[i] - x[a], y[i] - y[a], z[i] - z[a]}) / len(h)));
}
return ret;
}
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cout << fixed << setprecision(20);
cin >> n;
rep (i, n) cin >> x[i] >> y[i] >> z[i];
if (n <= 3) ans = 0;
// 3点で束縛
rep (i, n) rep (j, i + 1, n) rep (k, j + 1, n) {
auto v1 = make_vec(i, j);
auto v2 = make_vec(i, k);
if (v1 == v2) continue;
auto h = product(v1, v2);
int side[2] = {};
rep (a, n) {
ll d = dot(h, vec{x[a] - x[i], y[a] - y[i], z[a] - z[i]});
if (d < 0) side[0]++;
if (d > 0) side[1]++;
}
if (side[0] && side[1]) continue;
long double res = 0;
rep (a, n) {
chmax(res, abs((long double)dot(h, vec{x[a] - x[i], y[a] - y[i], z[a] - z[i]}) / len(h)));
}
chmin(ans, res);
}
// 2点2点で束縛
rep (a, n) rep (b, a + 1, n) rep(c, b + 1, n) rep (d, c + 1, n) {
chmin(ans, judge(a, b, c, d));
chmin(ans, judge(a, c, b, d));
chmin(ans, judge(a, d, c, b));
}
if (ans == inf) ans = 0;
cout << ans << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3904kb
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 0 0 -1 0 0 -1 0 0 -1 0 0 -1 0 0 -1 0 0 -1 0 0 -1 0 0 -1 0 0 -1 0 0 -1 0 0 -1 0 0 -1 0 0 -1 0 0 -1 0 0 -1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 -1 0 0 -1 0 0 -1 0 0 -1 0 0 -1 0 0 -1 0 ...
result:
wrong answer 1st numbers differ - expected: '1.0000000', found: '-1.0000000', error = '2.0000000'