QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#272828 | #6412. Classical Geometry Problem | ucup-team859# | WA | 1ms | 3732kb | C++17 | 8.7kb | 2023-12-02 19:33:56 | 2023-12-02 19:33:56 |
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';
for (auto p : ans) {
cout << v[p.first].x << ' ' << v[p.first].y << ' ' << v[p.first].z << ' ' << p.second << '\n';
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3732kb
input:
3 105 255 175 174 174 174 0 0 0
output:
3 0.0000000000 255.0000000000 255.0000000000 360.6244584051 255.0000000000 255.0000000000 255.0000000000 153.0000000000 0.0000000000 255.0000000000 0.0000000000 93.2952303175 2 0.0000000000 0.0000000000 0.0000000000 0.0000000000 255.0000000000 255.0000000000 255.0000000000 301.3768405170 1 0.0000000...
result:
wrong output format Expected integer, but "0.0000000000" found (test case 1)