QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#272855#6412. Classical Geometry Problemucup-team859WA 27ms3964kbC++179.0kb2023-12-02 19:40:372023-12-02 19:40:39

Judging History

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

  • [2023-12-02 19:40:39]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:3964kb
  • [2023-12-02 19:40:37]
  • 提交

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)