QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#487072#6412. Classical Geometry Problemucup-team1525#WA 1ms3804kbC++207.2kb2024-07-22 15:47:202024-07-22 15:47:21

Judging History

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

  • [2024-07-22 15:47:21]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3804kb
  • [2024-07-22 15:47:20]
  • 提交

answer

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

using db = long double;
const db eps = 1e-10;

int dcmp(const db x) {
    return abs(x) < eps ? 0 : (x < 0 ? -1 : 1);
}

struct Point2D {
    db x, y;
    Point2D(db x, db y) : x(x), y(y) {}
    Point2D() = default;
    Point2D operator+(const Point2D &a) const { return Point2D(x + a.x, y + a.y); }
    Point2D operator-(const Point2D &a) const { return Point2D(x - a.x, y - a.y); }
    Point2D operator*(const db &a) const { return Point2D(x * a, y * a); }
    Point2D operator/(const db &a) const { return Point2D(x / a, y / a); }
    db len() const { return hypotl(x, y); }
    db dis(const Point2D &a) const { return (*this - a).len(); }
    db operator^(const Point2D &a) const { return x * a.y - y * a.x; }
    db operator*(const Point2D &a) const { return x * a.x + y * a.y; }
};

struct Line2D {
    Point2D p, v;
    Line2D() = default;
    Line2D(Point2D p, Point2D v) : p(p), v(v) {}
    Point2D inter(const Line2D &a) const {
        return p + v * ((a.v ^ (p - a.p)) / (v ^ a.v));
    };
};

bool is_seg_cross(const Point2D &sx, const Point2D &sy, const Point2D &tx, const Point2D &ty) {
    auto p = Line2D(sx, sy - sx).inter(Line2D(tx, ty - tx));
    return (p - sx) * (sy - p) >= -eps && (p - tx) * (ty - p) >= -eps;
}

struct Point3D {
    db x, y, z;
    Point3D(db x, db y, db z) : x(x), y(y), z(z) {}
    Point3D operator+(const Point3D &a) const { return Point3D(x + a.x, y + a.y, z + a.z); }
    Point3D operator-(const Point3D &a) const { return Point3D(x - a.x, y - a.y, z - a.z); }
    Point3D operator*(const db &a) const { return Point3D(x * a, y * a, z * a); }
    Point3D operator/(const db &a) const { return Point3D(x / a, y / a, z / a); }
    db operator*(const Point3D &a) const { return x * a.x + y * a.y + z * a.z; }
    db len() const { return __hypot3(x, y, z); }
    db dis(const Point3D &a) const { return (*this - a).len(); }
};
struct Line3D {
    Point3D p1, p2;
};
using Vec3D = Point3D;
struct Plane {
    Point3D p1, p2, p3;
    Plane(Point3D p1, Point3D p2, Point3D p3) : p1(p1), p2(p2), p3(p3) {}
};
Point3D Cross(Point3D A, Point3D B) {
    return Point3D(A.y * B.z - A.z * B.y, A.z * B.x - A.x * B.z, A.x * B.y - A.y * B.x);
}
Point3D pvec(Plane f) {
    return Cross(f.p2 - f.p1, f.p3 - f.p1);
}
Point3D line_cross_p(Line3D u, Plane f) {
    Point3D v = pvec(f);
    db x = (v * (u.p2 - f.p1));
    db y = (v * (u.p1 - f.p1));
    db d = x - y;
    Point3D p = ((u.p1 * x) - (u.p2 * y)) / d;
    return p;
}

struct Move {
    int vx, vy, vz;
    db dis;
};
vector<Move> ans;
void add_move(int vx, int vy, int vz, db dis) {
    ans.push_back((Move){vx, vy, vz, dis});
}

const Line2D l[4] = {
    Line2D({0, 0}, {255, 0}),
    Line2D({255, 0}, {0, 255}),
    Line2D({255, 255}, {-255, 0}),
    Line2D({0, 255}, {0, -255}),
};

pair<Point2D, int> inter_plane(Point2D p) {
    Line2D pl = Line2D({0, 0}, p);
    auto ip = l[1].inter(pl);
    if (is_seg_cross({0, 0}, ip, l[1].p, l[1].p + l[1].v))
        return make_pair(ip, 1);
    ip = l[2].inter(pl);
    if (is_seg_cross({0, 0}, ip, l[2].p, l[2].p + l[2].v))
        return make_pair(ip, 2);
    assert(false);
}

void move_plane(Point3D p) {
    auto [x, y, z] = p;
    if (x == 0 || x == 255) {
        Point2D p2 = Point2D(y, z);
        auto [jp, lid] = inter_plane(p2);
        if (lid == 1)
            add_move(x, 255, 0, Point3D(x, 255, 0).dis({0, 0, 0})), add_move(x, 255, 255, Point3D(x, jp.x, jp.y).dis({x, 255, 0}));
        if (lid == 2)
            add_move(x, 0, 255, Point3D(x, 0, 255).dis({0, 0, 0})), add_move(x, 255, 255, Point3D(x, jp.x, jp.y).dis({x, 0, 255}));
        auto last_p = Point3D(x, jp.x, jp.y);
        add_move(x, 0, 0, last_p.dis(p));
    } else if (y == 0 || y == 255) {
        Point2D p2 = Point2D(x, z);
        auto [jp, lid] = inter_plane(p2);
        if (lid == 1)
            add_move(255, y, 0, Point3D(255, y, 0).dis({0, 0, 0})), add_move(255, y, 255, Point3D(jp.x, y, jp.y).dis({255, y, 0}));
        if (lid == 2)
            add_move(0, y, 255, Point3D(0, y, 255).dis({0, 0, 0})), add_move(255, y, 255, Point3D(jp.x, y, jp.y).dis({0, y, 255}));
        add_move(0, y, 0, Point3D(jp.x, y, jp.y).dis(p));
    } else {
        Point2D p2 = Point2D(x, y);
        auto [jp, lid] = inter_plane(p2);
        if (lid == 1)
            add_move(255, 0, z, Point3D(255, 0, z).dis({0, 0, 0})), add_move(255, 255, z, Point3D(jp.x, jp.y, z).dis({255, 0, z}));
        if (lid == 2)
            add_move(0, 255, z, Point3D(0, 255, z).dis({0, 0, 0})), add_move(255, 255, z, Point3D(jp.x, jp.y, z).dis({0, 255, z}));
        add_move(0, 0, z, Point3D(jp.x, jp.y, z).dis(p));
    }
}

void move_line(Point3D p) {
    auto [x, y, z] = p;
    if (dcmp(x) > 0 && dcmp(x - 255) < 0) {
        add_move(0, y, z, Point3D(0, y, z).dis({0, 0, 0}));
        add_move(255, y, z, Point3D(x, y, z).dis({0, y, z}));
    } else if (dcmp(y) > 0 && dcmp(y - 255) < 0) {
        add_move(x, 0, z, Point3D(x, 0, z).dis({0, 0, 0}));
        add_move(x, 255, z, Point3D(x, y, z).dis({x, 0, z}));
    } else if (dcmp(z) > 0 && dcmp(z - 255) < 0) {
        add_move(x, y, 0, Point3D(x, y, 0).dis({0, 0, 0}));
        add_move(x, y, 255, Point3D(x, y, z).dis({x, y, 0}));
    }
}

void solve() {
    ans.clear();
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    Point3D tp = Point3D(x, y, z);
    int cnt = (x == 0 || x == 255) + (y == 0 || y == 255) + (z == 0 || z == 255);
    if (cnt == 3) {
        add_move(x, y, z, Point3D(x, y, z).dis(Point3D{0, 0, 0}));
    } else if (cnt == 2) {
        move_line(Point3D{x, y, z});
    } else if (cnt == 1) {
        move_plane(Point3D(x, y, z));
    } else {
        auto p = Point3D{x, y, z};
        Line3D l3d = Line3D{Point3D{0, 0, 0}, p};
        Plane f1 = Plane{{0, 0, 255}, {255, 0, 255}, {255, 255, 255}};
        Plane f2 = Plane({255, 0, 0}, {255, 255, 0}, {255, 255, 255});
        Plane f3 = Plane({0, 255, 255}, {255, 255, 255}, {255, 255, 0});

        auto p1 = line_cross_p(l3d, f1), p2 = line_cross_p(l3d, f2), p3 = line_cross_p(l3d, f3);
        if (dcmp(p1.x - 255) <= 0 && dcmp(p1.y - 255 <= 0)) {
            if (dcmp(p1.x) == 0 || dcmp(p1.x - 255) == 0)
                move_line(p1);
            else if (dcmp(p1.y == 0) || dcmp(p1.y - 255) == 0)
                move_line(p1);
            else
                move_plane(p1);
        } else if (dcmp(p2.y - 255) <= 0 && dcmp(p2.z - 255 <= 0)) {
            if (dcmp(p2.y) == 0 || dcmp(p2.y - 255) == 0)
                move_line(p2);
            else if (dcmp(p2.z == 0) || dcmp(p2.z - 255) == 0)
                move_line(p2);
            else
                move_plane(p2);
        } else {
            if (dcmp(p3.x) == 0 || dcmp(p3.x - 255) == 0)
                move_line(p3);
            else if (dcmp(p3.z == 0) || dcmp(p3.z - 255) == 0)
                move_line(p3);
            else
                move_plane(p3);
        }
    }

    cout << ans.size() << "\n";
    for (auto &[vx, vy, vz, dis] : ans) {
        printf("%d %d %d %.12Lf\n", vx, vy, vz, dis);
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3804kb

input:

3
105 255 175
174 174 174
0 0 0

output:

3
0 255 255 360.624458405139
255 255 255 153.000000000000
0 255 0 93.295230317525
0
1
0 0 0 0.000000000000

result:

wrong answer too far from the target: (0.000000, 0.000000, 0.000000) instead of (174, 174, 174) (test case 2)