QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#487072 | #6412. Classical Geometry Problem | ucup-team1525# | WA | 1ms | 3804kb | C++20 | 7.2kb | 2024-07-22 15:47:20 | 2024-07-22 15:47:21 |
Judging History
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)