QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#193158 | #7521. Find the Gap | ucup-team1516# | WA | 26ms | 3904kb | C++20 | 5.0kb | 2023-09-30 16:29:58 | 2023-09-30 16:29:59 |
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) {}
// vec (int a, int b, int c) : x(a), y(b), z(c) {
// int g = gcd(x, gcd(y, z));
// if (x < 0) g *= -1;
// if (x == 0 && y < 0) g *= -1;
// if (x == 0 && y ==0 && z < 0) g *= -1;
// x /= g, y /= g, z /= g;
// }
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];
int 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) {
return vec{v1.y * v2.z - v1.z * v2.y, v1.z * v2.x - v1.x * v2.z, v1.x * v2.y - v1.y * v2.x};
}
ll dot(vec v1, vec v2) {
return v1.x * v2.x + v1.y * v2.y + v1.z * v2.z;
}
long double len(vec v) {
return sqrt(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));
}
cout << ans << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3836kb
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.00000000000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
5 1 1 1 1 2 1 1 1 2 1 2 2 2 1 1
output:
0.70710678118654747608
result:
ok found '0.707106781', expected '0.707106781', error '0.000000000'
Test #3:
score: -100
Wrong Answer
time: 26ms
memory: 3904kb
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:
1073741824.00000000000000000000
result:
wrong answer 1st numbers differ - expected: '0.0000000', found: '1073741824.0000000', error = '1073741824.0000000'