QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#193158#7521. Find the Gapucup-team1516#WA 26ms3904kbC++205.0kb2023-09-30 16:29:582023-09-30 16:29:59

Judging History

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

  • [2023-09-30 16:29:59]
  • 评测
  • 测评结果:WA
  • 用时:26ms
  • 内存:3904kb
  • [2023-09-30 16:29:58]
  • 提交

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'