QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#272855 | #6412. Classical Geometry Problem | ucup-team859 | WA | 27ms | 3964kb | C++17 | 9.0kb | 2023-12-02 19:40:37 | 2023-12-02 19:40:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-9;
struct Point {
double x, y, z;
}v[8];
vector <pair <int, double>> ans;
int sgn(double d) {
return (d > EPS) - (d < -EPS);
}
bool okPoint(Point p) {
return sgn(p.x) >= 0 && sgn(255 - p.x) >= 0 && sgn(p.y) >= 0 && sgn(255 - p.y) >= 0 && sgn(p.z) >= 0 && sgn(255 - p.z) >= 0;
}
void printPoint(Point p) {
cout << p.x << ' ' << p.y << ' ' << p.z << '\n';
}
double pointDist(Point a, Point b) {
double dx = (a.x - b.x) * (a.x - b.x);
double dy = (a.y - b.y) * (a.y - b.y);
double dz = (a.z - b.z) * (a.z - b.z);
return sqrt(dx + dy + dz);
}
Point moveToFace(Point p) {
for (int i = 7; i >= 0; i--) {
Point np;
/// x = 0:
np.x = 255 - v[i].x;
np.y = v[i].y - (v[i].x - np.x) / (p.x - v[i].x) * (p.y - v[i].y);
np.z = v[i].z - (v[i].x - np.x) / (p.x - v[i].x) * (p.z - v[i].z);
if (okPoint(np)) {
double dist = pointDist(v[i], np) * (p.x - np.x) / (v[i].x - np.x);
ans.push_back({i, dist});
return np;
}
np.y = 255 - v[i].y;
np.x = v[i].x - (v[i].y - np.y) / (p.y - v[i].y) * (p.x - v[i].x);
np.z = v[i].z - (v[i].y - np.y) / (p.y - v[i].y) * (p.z - v[i].z);
if (okPoint(np)) {
double dist = pointDist(v[i], np) * (p.x - np.x) / (v[i].x - np.x);
ans.push_back({i, dist});
return np;
}
np.z = 255 - v[i].z;
np.x = v[i].x - (v[i].z - np.z) / (p.z - v[i].z) * (p.x - v[i].x);
np.x = v[i].y - (v[i].z - np.z) / (p.z - v[i].z) * (p.y - v[i].y);
if (okPoint(np)) {
double dist = pointDist(v[i], np) * (p.x - np.x) / (v[i].x - np.x);
ans.push_back({i, dist});
return np;
}
}
cout << "EROARE MARE\n";
return {0, 0, 0};
}
void solveFace(Point p, vector <int> face) {
for (int i = 0; i < 4; i++) {
Point c = v[face[i]];
if (sgn(c.x - p.x) == 0 && sgn(c.y - p.y) == 0 && sgn(c.z - p.z) == 0) {
double dist = pointDist(c, v[0]);
ans.push_back({face[i], dist});
return;
}
}
for (int i = 0; i < 4; i++) {
Point c = v[face[i]];
Point c2 = c;
double dist;
if (sgn(c.x - p.x) == 0 && sgn(c.y - p.y) == 0) {
c2.z = 255 - c.z;
dist = pointDist(c, c2) * (p.z - c.z) / (c2.z - c.z);
int aux = face[i];
if (c.z == 0) aux += 4;
if (c.z == 255) aux -= 4;
ans.push_back({aux, dist});
dist = pointDist(c, v[0]);
ans.push_back({face[i], dist});
return;
}
if (sgn(c.x - p.x) == 0 && sgn(c.z - p.z) == 0) {
c2.y = 255 - c.y;
dist = pointDist(c, c2) * (p.y - c.y) / (c2.y - c.y);
int aux = face[i];
if (c.y == 0) aux += 2;
if (c.y == 255) aux -= 2;
ans.push_back({aux, dist});
dist = pointDist(c, v[0]);
ans.push_back({face[i], dist});
return;
}
if (sgn(c.y - p.y) == 0 && sgn(c.z - p.z) == 0) {
c2.x = 255 - c.x;
dist = pointDist(c, c2) * (p.x - c.x) / (c2.x - c.x);
int aux = face[i];
if (c.x == 0) aux++;
if (c.x == 255) aux--;
ans.push_back({aux, dist});
dist = pointDist(c, v[0]);
ans.push_back({face[i], dist});
return;
}
}
Point np;
for (int i = 0; i < 4; i++) {
Point c = v[face[i]];
if (sgn(c.x - p.x) == 0) {
np = p;
np.y = 255 - c.y;
np.z = c.z - (c.y - np.y) / (p.y - c.y) * (p.z - c.z);
if (sgn(np.z) >= 0 && sgn(255 - np.z) >= 0) {
double dist = pointDist(c, np) * (p.y - np.y) / (c.y - np.y);
ans.push_back({face[i], dist});
break;
}
np = p;
np.z = 255 - c.z;
np.y = c.y - (c.z - np.z) / (p.z - c.z) * (p.y - c.y);
if (sgn(np.y) >= 0 && sgn(255 - np.y) >= 0) {
double dist = pointDist(c, np) * (p.z - np.z) / (c.z - np.z);
ans.push_back({face[i], dist});
break;
}
}
if (sgn(c.y - p.y) == 0) {
np = p;
np.x = 255 - c.x;
np.z = c.z - (c.x - np.x) / (p.x - c.x) * (p.z - c.z);
if (sgn(np.z) >= 0 && sgn(255 - np.z) >= 0) {
double dist = pointDist(c, np) * (p.x - np.x) / (c.x - np.x);
ans.push_back({face[i], dist});
break;
}
np = p;
np.z = 255 - c.z;
np.x = c.x - (c.z - np.z) / (p.z - c.z) * (p.x - c.x);
if (sgn(np.x) >= 0 && sgn(255 - np.x) >= 0) {
double dist = pointDist(c, np) * (p.z - np.z) / (c.z - np.z);
ans.push_back({face[i], dist});
break;
}
}
if (sgn(c.z - p.z) == 0) {
np = p;
np.y = 255 - c.y;
np.x = c.x - (c.y - np.y) / (p.y - c.y) * (p.x - c.x);
if (sgn(np.x) >= 0 && sgn(255 - np.x) >= 0) {
double dist = pointDist(c, np) * (p.y - np.y) / (c.y - np.y);
ans.push_back({face[i], dist});
break;
}
np = p;
np.x = 255 - c.x;
np.y = c.y - (c.x - np.x) / (p.x - c.x) * (p.y - c.y);
if (sgn(np.y) >= 0 && sgn(255 - np.y) >= 0) {
double dist = pointDist(c, np) * (p.x - np.x) / (c.x - np.x);
ans.push_back({face[i], dist});
break;
}
}
}
p = np;
for (int i = 0; i < 4; i++) {
Point c = v[face[i]];
if (sgn(c.x - p.x) == 0 && sgn(c.y - p.y) == 0 && sgn(c.z - p.z) == 0) {
double dist = pointDist(c, v[0]);
ans.push_back({face[i], dist});
return;
}
}
for (int i = 0; i < 4; i++) {
Point c = v[face[i]];
Point c2 = c;
double dist;
if (sgn(c.x - p.x) == 0 && sgn(c.y - p.y) == 0) {
c2.z = 255 - c.z;
dist = pointDist(c, c2) * (p.z - c.z) / (c2.z - c.z);
int aux = face[i];
if (c.z == 0) aux += 4;
if (c.z == 255) aux -= 4;
ans.push_back({aux, dist});
dist = pointDist(c, v[0]);
ans.push_back({face[i], dist});
return;
}
if (sgn(c.x - p.x) == 0 && sgn(c.z - p.z) == 0) {
c2.y = 255 - c.y;
dist = pointDist(c, c2) * (p.y - c.y) / (c2.y - c.y);
int aux = face[i];
if (c.y == 0) aux += 2;
if (c.y == 255) aux -= 2;
ans.push_back({aux, dist});
dist = pointDist(c, v[0]);
ans.push_back({face[i], dist});
return;
}
if (sgn(c.y - p.y) == 0 && sgn(c.z - p.z) == 0) {
c2.x = 255 - c.x;
dist = pointDist(c, c2) * (p.x - c.x) / (c2.x - c.x);
int aux = face[i];
if (c.x == 0) aux++;
if (c.x == 255) aux--;
ans.push_back({aux, dist});
dist = pointDist(c, v[0]);
ans.push_back({face[i], dist});
return;
}
}
}
void solve() {
Point p;
cin >> p.x >> p.y >> p.z;
bool onFace = 0;
if (sgn(p.x) == 0 || sgn(p.x - 255) == 0 || sgn(p.y) == 0 || sgn(p.y - 255) == 0 || sgn(p.z) == 0 || sgn(p.z - 255) == 0) {
onFace = 1;
}
if (!onFace) {
p = moveToFace(p);
}
vector <int> face;
for (int i = 0; i < 8; i++) {
if (sgn(p.x - v[i].x) == 0 || sgn(p.y - v[i].y) == 0 || sgn(p.z - v[i].z) == 0) {
face.push_back(i);
}
}
solveFace(p, face);
reverse(ans.begin(), ans.end());
cout << ans.size() << '\n';
p = {0, 0, 0};
for (auto pr : ans) {
cout << (int) v[pr.first].x << ' ' << (int) v[pr.first].y << ' ' << (int) v[pr.first].z << ' ' << pr.second << '\n';
Point np = p;
np.x = p.x + (v[pr.first].x - p.x) * pr.second / pointDist(p, v[pr.first]);
np.y = p.y + (v[pr.first].y - p.y) * pr.second / pointDist(p, v[pr.first]);
np.z = p.z + (v[pr.first].z - p.z) * pr.second / pointDist(p, v[pr.first]);
//printPoint(np);
p = np;
}
ans.clear();
}
int main() {
#ifdef LOCAL
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif // LOCAL
ios_base::sync_with_stdio(false);
cin.tie(0);
for (int i = 0; i < 8; i++) {
v[i].x = ((i & 1) != 0) * 255;
v[i].y = ((i & 2) != 0) * 255;
v[i].z = ((i & 4) != 0) * 255;
}
int nrTeste;
cin >> nrTeste;
cout << fixed << setprecision(10);
while (nrTeste--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3952kb
input:
3 105 255 175 174 174 174 0 0 0
output:
3 0 255 255 360.6244584051 255 255 255 153.0000000000 0 255 0 93.2952303175 2 0 0 0 0.0000000000 255 255 255 301.3768405170 1 0 0 0 0.0000000000
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 27ms
memory: 3964kb
input:
10000 250 128 13 1 245 2 88 183 138 179 69 194 153 246 33 255 119 192 233 30 108 26 208 33 53 162 189 225 130 10 202 137 121 152 198 25 49 165 180 228 56 30 74 18 14 6 115 31 168 242 206 90 238 139 44 103 60 16 21 190 229 209 68 41 171 181 39 74 73 181 96 18 234 95 70 75 174 84 101 16 44 202 249 80 ...
output:
3 0 0 0 0.0000000000 255 0 0 121.1776859504 255 255 255 370.2818212173 4 0 255 0 255.0000000000 0 255 255 1.0450819672 0 0 0 10.0394543918 255 255 255 1.4119814048 4 0 255 0 255.0000000000 0 255 255 134.2105263158 0 0 0 124.2376040857 255 255 255 113.9495828874 4 0 0 255 255.0000000000 255 0 255 224...
result:
wrong answer too far from the target: (250.000000, 245.472441, 245.472441) instead of (250, 128, 13) (test case 1)