QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#106374 | #6412. Classical Geometry Problem | maspy | WA | 49ms | 3708kb | C++23 | 15.5kb | 2023-05-17 15:41:19 | 2023-05-17 15:41:24 |
Judging History
answer
#line 1 "library/my_template.hpp"
#if defined(LOCAL)
#include <my_template_compiled.hpp>
#else
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;
template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'000'000'000;
template <>
constexpr ll infty<ll> = ll(infty<int>) * infty<int> * 2;
template <>
constexpr u32 infty<u32> = infty<int>;
template <>
constexpr u64 infty<u64> = infty<ll>;
template <>
constexpr i128 infty<i128> = i128(infty<ll>) * infty<ll>;
template <>
constexpr double infty<double> = infty<ll>;
template <>
constexpr long double infty<long double> = infty<ll>;
using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
#define vv(type, name, h, ...) \
vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) \
vector<vector<vector<type>>> name( \
h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
vector<vector<vector<vector<type>>>> name( \
a, vector<vector<vector<type>>>( \
b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
// https://trap.jp/post/1224/
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define FOR_subset(t, s) \
for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define stoi stoll
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
template <typename T, typename U>
T ceil(T x, U y) {
return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U>
T floor(T x, U y) {
return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T, typename U>
pair<T, T> divmod(T x, U y) {
T q = floor(x, y);
return {q, x - q * y};
}
template <typename T, typename U>
T SUM(const vector<U> &A) {
T sum = 0;
for (auto &&a: A) sum += a;
return sum;
}
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) \
sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()
template <typename T>
T POP(deque<T> &que) {
T a = que.front();
que.pop_front();
return a;
}
template <typename T>
T POP(pq<T> &que) {
T a = que.top();
que.pop();
return a;
}
template <typename T>
T POP(pqg<T> &que) {
assert(!que.empty());
T a = que.top();
que.pop();
return a;
}
template <typename T>
T POP(vc<T> &que) {
assert(!que.empty());
T a = que.back();
que.pop_back();
return a;
}
template <typename F>
ll binary_search(F check, ll ok, ll ng, bool check_ok = true) {
if (check_ok) assert(check(ok));
while (abs(ok - ng) > 1) {
auto x = (ng + ok) / 2;
tie(ok, ng) = (check(x) ? mp(x, ng) : mp(ok, x));
}
return ok;
}
template <typename F>
double binary_search_real(F check, double ok, double ng, int iter = 100) {
FOR(iter) {
double x = (ok + ng) / 2;
tie(ok, ng) = (check(x) ? mp(x, ng) : mp(ok, x));
}
return (ok + ng) / 2;
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
// ? は -1
vc<int> s_to_vi(const string &S, char first_char) {
vc<int> A(S.size());
FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); }
return A;
}
template <typename T, typename U>
vector<T> cumsum(vector<U> &A, int off = 1) {
int N = A.size();
vector<T> B(N + 1);
FOR(i, N) { B[i + 1] = B[i] + A[i]; }
if (off == 0) B.erase(B.begin());
return B;
}
// stable sort
template <typename T>
vector<int> argsort(const vector<T> &A) {
vector<int> ids(len(A));
iota(all(ids), 0);
sort(all(ids),
[&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
return ids;
}
// A[I[0]], A[I[1]], ...
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
vc<T> B(len(I));
FOR(i, len(I)) B[i] = A[I[i]];
return B;
}
#endif
#line 1 "library/other/io.hpp"
// based on yosupo's fastio
#include <unistd.h>
namespace fastio {
#define FASTIO
// クラスが read(), print() を持っているかを判定するメタ関数
struct has_write_impl {
template <class T>
static auto check(T &&x) -> decltype(x.write(), std::true_type{});
template <class T>
static auto check(...) -> std::false_type;
};
template <class T>
class has_write : public decltype(has_write_impl::check<T>(std::declval<T>())) {
};
struct has_read_impl {
template <class T>
static auto check(T &&x) -> decltype(x.read(), std::true_type{});
template <class T>
static auto check(...) -> std::false_type;
};
template <class T>
class has_read : public decltype(has_read_impl::check<T>(std::declval<T>())) {};
struct Scanner {
FILE *fp;
char line[(1 << 15) + 1];
size_t st = 0, ed = 0;
void reread() {
memmove(line, line + st, ed - st);
ed -= st;
st = 0;
ed += fread(line + ed, 1, (1 << 15) - ed, fp);
line[ed] = '\0';
}
bool succ() {
while (true) {
if (st == ed) {
reread();
if (st == ed) return false;
}
while (st != ed && isspace(line[st])) st++;
if (st != ed) break;
}
if (ed - st <= 50) {
bool sep = false;
for (size_t i = st; i < ed; i++) {
if (isspace(line[i])) {
sep = true;
break;
}
}
if (!sep) reread();
}
return true;
}
template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
bool read_single(T &ref) {
if (!succ()) return false;
while (true) {
size_t sz = 0;
while (st + sz < ed && !isspace(line[st + sz])) sz++;
ref.append(line + st, sz);
st += sz;
if (!sz || st != ed) break;
reread();
}
return true;
}
template <class T, enable_if_t<is_integral<T>::value, int> = 0>
bool read_single(T &ref) {
if (!succ()) return false;
bool neg = false;
if (line[st] == '-') {
neg = true;
st++;
}
ref = T(0);
while (isdigit(line[st])) { ref = 10 * ref + (line[st++] & 0xf); }
if (neg) ref = -ref;
return true;
}
template <typename T,
typename enable_if<has_read<T>::value>::type * = nullptr>
inline bool read_single(T &x) {
x.read();
return true;
}
bool read_single(double &ref) {
string s;
if (!read_single(s)) return false;
ref = std::stod(s);
return true;
}
bool read_single(char &ref) {
string s;
if (!read_single(s) || s.size() != 1) return false;
ref = s[0];
return true;
}
template <class T>
bool read_single(vector<T> &ref) {
for (auto &d: ref) {
if (!read_single(d)) return false;
}
return true;
}
template <class T, class U>
bool read_single(pair<T, U> &p) {
return (read_single(p.first) && read_single(p.second));
}
template <size_t N = 0, typename T>
void read_single_tuple(T &t) {
if constexpr (N < std::tuple_size<T>::value) {
auto &x = std::get<N>(t);
read_single(x);
read_single_tuple<N + 1>(t);
}
}
template <class... T>
bool read_single(tuple<T...> &tpl) {
read_single_tuple(tpl);
return true;
}
void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
bool f = read_single(h);
assert(f);
read(t...);
}
Scanner(FILE *fp) : fp(fp) {}
};
struct Printer {
Printer(FILE *_fp) : fp(_fp) {}
~Printer() { flush(); }
static constexpr size_t SIZE = 1 << 15;
FILE *fp;
char line[SIZE], small[50];
size_t pos = 0;
void flush() {
fwrite(line, 1, pos, fp);
pos = 0;
}
void write(const char val) {
if (pos == SIZE) flush();
line[pos++] = val;
}
template <class T, enable_if_t<is_integral<T>::value, int> = 0>
void write(T val) {
if (pos > (1 << 15) - 50) flush();
if (val == 0) {
write('0');
return;
}
if (val < 0) {
write('-');
val = -val; // todo min
}
size_t len = 0;
while (val) {
small[len++] = char(0x30 | (val % 10));
val /= 10;
}
for (size_t i = 0; i < len; i++) { line[pos + i] = small[len - 1 - i]; }
pos += len;
}
void write(const string s) {
for (char c: s) write(c);
}
void write(const char *s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; i++) write(s[i]);
}
void write(const double x) {
ostringstream oss;
oss << fixed << setprecision(15) << x;
string s = oss.str();
write(s);
}
void write(const long double x) {
ostringstream oss;
oss << fixed << setprecision(15) << x;
string s = oss.str();
write(s);
}
template <typename T,
typename enable_if<has_write<T>::value>::type * = nullptr>
inline void write(T x) {
x.write();
}
template <class T>
void write(const vector<T> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) write(' ');
write(val[i]);
}
}
template <class T, class U>
void write(const pair<T, U> val) {
write(val.first);
write(' ');
write(val.second);
}
template <size_t N = 0, typename T>
void write_tuple(const T t) {
if constexpr (N < std::tuple_size<T>::value) {
if constexpr (N > 0) { write(' '); }
const auto x = std::get<N>(t);
write(x);
write_tuple<N + 1>(t);
}
}
template <class... T>
bool write(tuple<T...> tpl) {
write_tuple(tpl);
return true;
}
template <class T, size_t S>
void write(const array<T, S> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) write(' ');
write(val[i]);
}
}
void write(i128 val) {
string s;
bool negative = 0;
if (val < 0) {
negative = 1;
val = -val;
}
while (val) {
s += '0' + int(val % 10);
val /= 10;
}
if (negative) s += "-";
reverse(all(s));
if (len(s) == 0) s = "0";
write(s);
}
};
Scanner scanner = Scanner(stdin);
Printer printer = Printer(stdout);
void flush() { printer.flush(); }
void print() { printer.write('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
printer.write(head);
if (sizeof...(Tail)) printer.write(' ');
print(forward<Tail>(tail)...);
}
void read() {}
template <class Head, class... Tail>
void read(Head &head, Tail &... tail) {
scanner.read(head);
read(tail...);
}
} // namespace fastio
using fastio::print;
using fastio::flush;
using fastio::read;
#define INT(...) \
int __VA_ARGS__; \
read(__VA_ARGS__)
#define LL(...) \
ll __VA_ARGS__; \
read(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
read(__VA_ARGS__)
#define CHAR(...) \
char __VA_ARGS__; \
read(__VA_ARGS__)
#define DBL(...) \
double __VA_ARGS__; \
read(__VA_ARGS__)
#define VEC(type, name, size) \
vector<type> name(size); \
read(name)
#define VV(type, name, h, w) \
vector<vector<type>> name(h, vector<type>(w)); \
read(name)
void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }
#line 3 "main.cpp"
using Re = double;
using T = tuple<Re, Re, Re, Re>;
const int B = 255;
void simu(vc<T> dat) {
Re x = 0, y = 0, z = 0;
for (auto&& [x1, y1, z1, d]: dat) {
Re dx = x1 - x, dy = y1 - y, dz = z1 - z;
Re norm = sqrt(dx * dx + dy * dy + dz * dz);
Re t = d / norm;
x += t * dx;
y += t * dy;
z += t * dz;
}
print(x, y, z);
}
Re dist(Re x, Re y, Re z, Re x1, Re y1, Re z1) {
Re dx = x - x1, dy = y - y1, dz = z - z1;
return sqrt(dx * dx + dy * dy + dz * dz);
}
void solve() {
Re x, y, z;
read(x), read(y), read(z);
x /= B, y /= B, z /= B;
auto dfs = [&](auto& dfs, Re x, Re y, Re z) -> vc<T> {
if (x > y) {
auto dat = dfs(dfs, y, x, z);
for (auto&& [a, b, c, d]: dat) swap(a, b);
return dat;
}
if (y > z) {
auto dat = dfs(dfs, x, z, y);
for (auto&& [a, b, c, d]: dat) swap(b, c);
return dat;
}
assert(x <= y && y <= z);
// to x=0
if (x > 0) {
Re t = x;
Re x1 = 1.0 - (1.0 - x) / (1.0 - t);
Re y1 = 1.0 - (1.0 - y) / (1.0 - t);
Re z1 = 1.0 - (1.0 - z) / (1.0 - t);
Re d = dist(x, y, z, x1, y1, z1);
auto dat = dfs(dfs, x1, y1, z1);
dat.eb(1, 1, 1, d);
return dat;
}
if (y > 0) {
Re t = y;
Re x1 = 0.0;
Re y1 = 1.0 - (1.0 - y) / (1.0 - t);
Re z1 = 1.0 - (1.0 - z) / (1.0 - t);
Re d = dist(x, y, z, x1, y1, z1);
auto dat = dfs(dfs, x1, y1, z1);
dat.eb(0, 1, 1, d);
return dat;
}
if (z > 0) {
Re t = z;
Re x1 = 0.0;
Re y1 = 0.0;
Re z1 = 0.0;
Re d = dist(x, y, z, x1, y1, z1);
auto dat = dfs(dfs, x1, y1, z1);
dat.eb(0, 0, 1, d);
return dat;
}
return {};
};
auto dat = dfs(dfs, x, y, z);
for (auto&& [a, b, c, d]: dat) {
a = int(B * a + 0.5);
b = int(B * b + 0.5);
c = int(B * c + 0.5);
d *= B;
}
// simu(dat);
print(len(dat));
for (auto&& [a, b, c, d]: dat) print(int(a), int(b), int(c), d);
}
signed main() {
INT(T);
FOR(T) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3576kb
input:
3 105 255 175 174 174 174 0 0 0
output:
3 0 255 0 255.000000000000000 0 255 255 119.000000000000000 255 255 255 119.000000000000000 1 255 255 255 301.376840516984601 0
result:
ok ok (3 test cases)
Test #2:
score: 0
Accepted
time: 46ms
memory: 3600kb
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.960629921259823 255 255 0 121.271562481707207 255 255 255 14.683872523534538 3 0 255 0 244.920948616600811 0 255 255 1.004720917329022 255 255 255 1.411981404758213 3 0 255 0 98.076923076923094 0 255 255 89.645464491727452 255 255 255 113.949582887386640 3 0 0 255 50.328947368421069 25...
result:
ok ok (10000 test cases)
Test #3:
score: 0
Accepted
time: 46ms
memory: 3708kb
input:
10000 90 173 87 39 251 59 39 43 150 106 29 130 52 55 180 236 225 70 171 15 48 92 133 240 182 226 10 126 139 105 196 7 204 32 131 193 27 96 218 67 29 33 159 9 251 130 111 243 226 69 39 198 131 80 108 169 147 45 36 170 76 138 251 55 235 186 224 165 48 51 133 173 225 14 226 234 70 139 178 92 174 138 24...
output:
4 0 255 0 128.272727272727309 255 255 0 5.084891638574913 255 255 255 0.000000000000069 255 255 255 129.125162988616324 3 0 255 0 249.795918367346900 0 255 255 23.616027532010040 255 255 255 52.667780110124191 3 0 0 255 128.702830188679201 0 255 255 5.269681089668931 255 255 255 57.841219509815964 3...
result:
ok ok (10000 test cases)
Test #4:
score: -100
Wrong Answer
time: 49ms
memory: 3664kb
input:
10000 186 217 161 76 0 116 246 159 161 32 245 65 206 120 71 217 76 204 109 255 245 157 59 192 55 35 87 27 147 199 190 134 31 169 64 105 5 27 255 161 2 35 244 255 232 253 106 199 28 151 129 50 24 20 172 236 234 74 51 150 179 68 178 69 42 192 152 1 23 177 169 71 216 190 125 136 223 193 255 168 49 74 2...
output:
4 0 255 0 114.565217391304316 255 255 0 77.423738456576189 255 255 255 0.000000000000049 255 255 255 210.056622440366709 2 0 0 255 56.983240223463653 255 0 255 96.223583047615705 3 255 0 0 230.585106382978722 255 0 255 5.336794410424321 255 255 255 223.028684131240198 3 0 255 0 241.578947368421041 0...
result:
wrong output format Expected double, but "-nan" found (test case 9326)