QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#167785 | #6412. Classical Geometry Problem | realIyxiang# | WA | 27ms | 3712kb | C++14 | 3.1kb | 2023-09-07 17:26:12 | 2023-09-07 17:26:14 |
Judging History
answer
#include <bits/stdc++.h>
#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)
using namespace std;
using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;
template < typename T > T read() {
T x = 0; bool f = 0; char ch = getchar();
while(!isdigit(ch)) f |= ch == '-', ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return f ? -x : x;
}
template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }
const int N = 1e6 + 10;
const db eps = 1e-7;
const db tps = 1e-7;
bool cqu(db x, db y) { return fabs(x - y) < eps; }
struct ve {
db x, y, z;
ve(db _x, db _y, db _z) : x(_x), y(_y), z(_z) { }
db len() { return sqrt(x * x + y * y + z * z); }
friend ve operator - (ve a, ve b) { return ve(a.x - b.x, a.y - b.y, a.z - b.z); }
friend ve operator + (ve a, ve b) { return ve(a.x + b.x, a.y + b.y, a.z + b.z); }
friend ve operator * (ve a, db b) { return ve(a.x * b, a.y * b, a.z * b); }
friend bool operator == (ve a, ve b) {
return cqu(a.x, b.x) & cqu(a.y, b.y) & cqu(a.z, b.z);
}
void set1() { db t = len(); t = 1 / t; x *= t, y *= t, z *= t; }
};
void solve() {
ve t(0, 0, 0); t.x = in, t.y = in, t.z = in;
vector < pair < db, ve > > ans;
auto output = [&]() {
printf("%d\n", ans.size());
ve cur(0, 0, 0);
for(auto v : ans) {
//if(v.fi < 0) continue;
ve t = (v.se - cur); db le = min(t.len(), v.fi); t.set1();
cur = cur + t * le;
}
//cerr << "!" << cur.x << " " << cur.y << " " << cur.z << endl;
//for(auto v : ans) assert(v.fi >= 0 && v.fi <= 10000);
for(auto v : ans) printf("%.0lf %.0lf %.0lf %.11lf\n", v.se.x, v.se.y, v.se.z, v.fi);
};
ve g1(255 + tps, 255 + tps, 255 + tps);
if(g1 == t) return output();
auto dt = [&](db x) { return cqu(x, 0) || x < 0 ? 1e4 : x; };
ve p = g1 - t; p.set1();
db ret = min({ dt(t.x / p.x), dt(t.y / p.y), dt(t.z / p.z) });
if(cqu(ret, 1e4) || cqu(t.x, 0) || cqu(t.y, 0) || cqu(t.z, 0)) { }
else {
ans.eb(ret, g1); // reverse pos
t = t - p * ret;
//cerr << "!G" << t.x << " " << t.y << " " << t.z << endl;
}
ve g2 = g1;
if(cqu(t.x, 0)) g2.x = tps; if(cqu(t.y, 0)) g2.y = tps; if(cqu(t.z, 0)) g2.z = tps;
//if(t == ve(0, 0, 0)) return output();
p = g2 - t; p.set1();
ret = min({ dt(t.x / p.x), dt(t.y / p.y), dt(t.z / p.z) });
if(cqu(ret, 1e4)) { }
else {
ans.eb(ret, g2);
t = t - p * ret;
//cerr << "!G" << t.x << " " << t.y << " " << t.z << endl;
}
ve g3 = g2;
if(cqu(t.x, 0)) g3.x = tps; if(cqu(t.y, 0)) g3.y = tps; if(cqu(t.z, 0)) g3.z = tps;
ans.eb(t.len(), g3);
g3.set1();
t = t - g3 * ans.back().fi;
reverse(ans.begin(), ans.end()); output();
}
int main() {
#ifdef YJR_2333_TEST
freopen("1.in", "r", stdin);
#endif
for(int T = in; T; T--) solve(); return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3684kb
input:
3 105 255 175 174 174 174 0 0 0
output:
3 0 255 0 254.99999978125 0 255 255 118.99999996733 255 255 255 119.00000001537 2 0 0 0 0.00000000000 255 255 255 301.37684051698 1 0 0 0 0.00000000000
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 27ms
memory: 3712kb
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 255 0 0 244.96062982444 255 255 0 121.27156248276 255 255 255 14.68387252482 3 0 255 0 244.92094861584 0 255 255 1.00472091734 255 255 255 1.41198140477 3 0 255 0 98.07692303156 0 255 255 89.64546448636 255 255 255 113.94958290590 3 0 0 255 50.32894732194 255 0 255 193.37465331004 255 255 255 77.8...
result:
wrong answer too far from the target: (173.286711, 173.286711, 35.578999) instead of (228, 56, 30) (test case 14)