QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#193413#7521. Find the Gapucup-team1516#WA 2ms3904kbC++204.9kb2023-09-30 17:06:372023-09-30 17:06:37

Judging History

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

  • [2023-09-30 17:06:37]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3904kb
  • [2023-09-30 17:06:37]
  • 提交

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'