QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#805629 | #7073. Absolute Space | SGColin | AC ✓ | 1ms | 4272kb | C++20 | 2.9kb | 2024-12-08 17:42:25 | 2024-12-08 17:42:26 |
Judging History
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