QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#805629#7073. Absolute SpaceSGColinAC ✓1ms4272kbC++202.9kb2024-12-08 17:42:252024-12-08 17:42:26

Judging History

This is the latest submission verdict.

  • [2024-12-08 17:42:26]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 4272kb
  • [2024-12-08 17:42:25]
  • Submitted

answer

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

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define pb push_back

const double eps = 1e-4;
#define z(x)   (abs((x)) <= eps)
#define sqr(x) ((x) * (x)) 

#define letp const P

struct P {
    double x, y, z;
    P operator + (letp &p) const {return {x + p.x, y + p.y, z + p.z};} 
    P operator - (letp &p) const {return {x - p.x, y - p.y, z - p.z};} 
    bool operator == (letp &p) const {return x == p.x && y == p.y && z == p.z;}
    P rotx(double ang) const { 
        double cosa = cos(ang), sina = sin(ang);
        return {x, y * cosa - z * sina, y * sina + z * cosa};
    }
    P roty(double ang) const { 
        double cosa = cos(ang), sina = sin(ang);
        return {x * cosa - z * sina, y, x * sina + z * cosa};
    } 
    P rotz(double ang) const { 
        double cosa = cos(ang), sina = sin(ang);
        return {x * cosa - y * sina, x * sina + y * cosa, z};
    } 
    inline double dis(letp &p) {
        return sqrt(sqr(x - p.x) + sqr(y - p.y) + sqr(z - p.z));
    }
};

inline bool check(vector<P> &s, int n) {
    for (auto x : s) {
        int cnt = 0;
        for (auto y : s) { 
            if (x == y) continue;
            double d = x.dis(y);
            if (z(d)) return false;
            if (z(d - 1.0)) ++cnt;
        }
        if (cnt != n) return false;
    }
    return true;
}

inline vector<P> random_rotate(vector<P> &s) {
    vector<P> res = s;
    double ang = 360.0 * rand() / RAND_MAX;
    for (auto &x : res) x = x.rotx(ang); 
    ang = 360.0 * rand() / RAND_MAX;
    for (auto &x : res) x = x.roty(ang); 
    ang = 360.0 * rand() / RAND_MAX;
    for (auto &x : res) x = x.rotz(ang); 
    return res;
}

vector<P> ans[11];

int main() {
    ans[1].pb({0, 0, 0}); ans[1].pb({1, 0, 0});
    ans[2] = ans[1]; ans[2].pb({0.5, sqrt(3) / 2, 0});
    ans[3] = ans[2]; ans[3].pb({0.5, sqrt(3) / 6, sqrt(6) / 3});
    ans[4].pb({0, 0, 0}); ans[4].pb({1, 0, 0}); 
    ans[4].pb({0, 1, 0}); ans[4].pb({1, 1, 0});
    ans[4].pb({0.5, 0.5, sqrt(2) / 2}); ans[4].pb({0.5, 0.5, -sqrt(2) / 2});
    for (int i = 5; i <= 10; ++i) {
        int x = 1, nw = 100;
        for (int j = 1; j < i; ++j)
            if (ans[j].size() * ans[i - j].size() < nw) {
                nw = ans[j].size() * ans[i - j].size(); x = j;
            }
        vector<P> p;
        while (true) {
            ans[i].clear();
            p = random_rotate(ans[x]);
            for (auto a : p)
                for (auto b : ans[i - x]) ans[i].pb(a + b);
            if (check(ans[i], i)) break;
        }
    }

    int n = rd();
    printf("%d\n", (int)ans[n].size());
    for (auto x : ans[n]) printf("%.10lf %.10lf %.10lf\n", x.x, x.y, x.z);
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4272kb

input:

1

output:

2
0.0000000000 0.0000000000 0.0000000000
1.0000000000 0.0000000000 0.0000000000

result:

ok required_n=1, sz=2

Test #2:

score: 0
Accepted
time: 0ms
memory: 4068kb

input:

2

output:

3
0.0000000000 0.0000000000 0.0000000000
1.0000000000 0.0000000000 0.0000000000
0.5000000000 0.8660254038 0.0000000000

result:

ok required_n=2, sz=3

Test #3:

score: 0
Accepted
time: 0ms
memory: 4080kb

input:

3

output:

4
0.0000000000 0.0000000000 0.0000000000
1.0000000000 0.0000000000 0.0000000000
0.5000000000 0.8660254038 0.0000000000
0.5000000000 0.2886751346 0.8164965809

result:

ok required_n=3, sz=4

Test #4:

score: 0
Accepted
time: 0ms
memory: 4212kb

input:

4

output:

6
0.0000000000 0.0000000000 0.0000000000
1.0000000000 0.0000000000 0.0000000000
0.0000000000 1.0000000000 0.0000000000
1.0000000000 1.0000000000 0.0000000000
0.5000000000 0.5000000000 0.7071067812
0.5000000000 0.5000000000 -0.7071067812

result:

ok required_n=4, sz=6

Test #5:

score: 0
Accepted
time: 0ms
memory: 4084kb

input:

5

output:

12
0.0000000000 0.0000000000 0.0000000000
1.0000000000 0.0000000000 0.0000000000
0.0000000000 1.0000000000 0.0000000000
1.0000000000 1.0000000000 0.0000000000
0.5000000000 0.5000000000 0.7071067812
0.5000000000 0.5000000000 -0.7071067812
-0.5560746068 0.6051299375 -0.5697357198
0.4439253932 0.605129...

result:

ok required_n=5, sz=12

Test #6:

score: 0
Accepted
time: 1ms
memory: 4088kb

input:

6

output:

16
0.0000000000 0.0000000000 0.0000000000
1.0000000000 0.0000000000 0.0000000000
0.5000000000 0.8660254038 0.0000000000
0.5000000000 0.2886751346 0.8164965809
-0.0432700109 0.0936900096 0.9946606900
0.9567299891 0.0936900096 0.9946606900
0.4567299891 0.9597154134 0.9946606900
0.4567299891 0.38236514...

result:

ok required_n=6, sz=16

Test #7:

score: 0
Accepted
time: 0ms
memory: 4220kb

input:

7

output:

24
0.0000000000 0.0000000000 0.0000000000
1.0000000000 0.0000000000 0.0000000000
0.0000000000 1.0000000000 0.0000000000
1.0000000000 1.0000000000 0.0000000000
0.5000000000 0.5000000000 0.7071067812
0.5000000000 0.5000000000 -0.7071067812
0.8572362415 -0.5046547265 0.1023212256
1.8572362415 -0.504654...

result:

ok required_n=7, sz=24

Test #8:

score: 0
Accepted
time: 0ms
memory: 4080kb

input:

8

output:

36
0.0000000000 0.0000000000 0.0000000000
1.0000000000 0.0000000000 0.0000000000
0.0000000000 1.0000000000 0.0000000000
1.0000000000 1.0000000000 0.0000000000
0.5000000000 0.5000000000 0.7071067812
0.5000000000 0.5000000000 -0.7071067812
-0.5902419476 -0.1189487424 0.7984144538
0.4097580524 -0.11894...

result:

ok required_n=8, sz=36

Test #9:

score: 0
Accepted
time: 1ms
memory: 4124kb

input:

9

output:

64
0.0000000000 0.0000000000 0.0000000000
1.0000000000 0.0000000000 0.0000000000
0.5000000000 0.8660254038 0.0000000000
0.5000000000 0.2886751346 0.8164965809
-0.0432700109 0.0936900096 0.9946606900
0.9567299891 0.0936900096 0.9946606900
0.4567299891 0.9597154134 0.9946606900
0.4567299891 0.38236514...

result:

ok required_n=9, sz=64

Test #10:

score: 0
Accepted
time: 1ms
memory: 4000kb

input:

10

output:

96
0.0000000000 0.0000000000 0.0000000000
1.0000000000 0.0000000000 0.0000000000
0.0000000000 1.0000000000 0.0000000000
1.0000000000 1.0000000000 0.0000000000
0.5000000000 0.5000000000 0.7071067812
0.5000000000 0.5000000000 -0.7071067812
0.8572362415 -0.5046547265 0.1023212256
1.8572362415 -0.504654...

result:

ok required_n=10, sz=96