QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#761542 | #8779. Square of Triangles | maspy | WA | 511ms | 3752kb | C++23 | 28.3kb | 2024-11-19 00:33:23 | 2024-11-19 00:33:23 |
Judging History
answer
#line 1 "/home/maspy/compro/library/my_template.hpp"
#if defined(LOCAL)
#include <my_template_compiled.hpp>
#else
// https://codeforces.com/blog/entry/96344
#pragma GCC optimize("Ofast,unroll-loops")
// いまの CF だとこれ入れると動かない?
// #pragma GCC target("avx2,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i128 = __int128;
using u128 = unsigned __int128;
using f128 = __float128;
template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'010'000'000;
template <>
constexpr ll infty<ll> = 2'020'000'000'000'000'000;
template <>
constexpr u32 infty<u32> = infty<int>;
template <>
constexpr u64 infty<u64> = infty<ll>;
template <>
constexpr i128 infty<i128> = i128(infty<ll>) * 2'000'000'000'000'000'000;
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); }
int popcnt_sgn(int x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(ll x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(u64 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
// (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>
T kth_bit(int k) {
return T(1) << k;
}
template <typename T>
bool has_kth_bit(T x, int k) {
return x >> k & 1;
}
template <typename T>
T floor(T a, T b) {
return a / b - (a % b && (a ^ b) < 0);
}
template <typename T>
T ceil(T x, T y) {
return floor(x + y - 1, y);
}
template <typename T>
T bmod(T x, T y) {
return x - y * floor(x, y);
}
template <typename T>
pair<T, T> divmod(T x, T y) {
T q = floor(x, y);
return {q, x - q * y};
}
template <typename T, typename U>
T SUM(const vector<U> &A) {
T sm = 0;
for (auto &&a: A) sm += a;
return sm;
}
#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) {
T a = que.top();
que.pop();
return a;
}
template <typename T>
T POP(vc<T> &que) {
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;
(check(x) ? ok : ng) = 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;
(check(x) ? ok : ng) = 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;
}
template <typename T, typename... Vectors>
void concat(vc<T> &first, const Vectors &... others) {
vc<T> &res = first;
(res.insert(res.end(), others.begin(), others.end()), ...);
}
#endif
#line 1 "/home/maspy/compro/library/other/io.hpp"
#define FASTIO
#include <unistd.h>
// https://judge.yosupo.jp/submission/21623
namespace fastio {
static constexpr uint32_t SZ = 1 << 17;
char ibuf[SZ];
char obuf[SZ];
char out[100];
// pointer of ibuf, obuf
uint32_t pil = 0, pir = 0, por = 0;
struct Pre {
char num[10000][4];
constexpr Pre() : num() {
for (int i = 0; i < 10000; i++) {
int n = i;
for (int j = 3; j >= 0; j--) {
num[i][j] = n % 10 | '0';
n /= 10;
}
}
}
} constexpr pre;
inline void load() {
memcpy(ibuf, ibuf + pil, pir - pil);
pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin);
pil = 0;
if (pir < SZ) ibuf[pir++] = '\n';
}
inline void flush() {
fwrite(obuf, 1, por, stdout);
por = 0;
}
void rd(char &c) {
do {
if (pil + 1 > pir) load();
c = ibuf[pil++];
} while (isspace(c));
}
void rd(string &x) {
x.clear();
char c;
do {
if (pil + 1 > pir) load();
c = ibuf[pil++];
} while (isspace(c));
do {
x += c;
if (pil == pir) load();
c = ibuf[pil++];
} while (!isspace(c));
}
template <typename T>
void rd_real(T &x) {
string s;
rd(s);
x = stod(s);
}
template <typename T>
void rd_integer(T &x) {
if (pil + 100 > pir) load();
char c;
do
c = ibuf[pil++];
while (c < '-');
bool minus = 0;
if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
if (c == '-') { minus = 1, c = ibuf[pil++]; }
}
x = 0;
while ('0' <= c) { x = x * 10 + (c & 15), c = ibuf[pil++]; }
if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
if (minus) x = -x;
}
}
void rd(int &x) { rd_integer(x); }
void rd(ll &x) { rd_integer(x); }
void rd(i128 &x) { rd_integer(x); }
void rd(u32 &x) { rd_integer(x); }
void rd(u64 &x) { rd_integer(x); }
void rd(u128 &x) { rd_integer(x); }
void rd(double &x) { rd_real(x); }
void rd(long double &x) { rd_real(x); }
void rd(f128 &x) { rd_real(x); }
template <class T, class U>
void rd(pair<T, U> &p) {
return rd(p.first), rd(p.second);
}
template <size_t N = 0, typename T>
void rd_tuple(T &t) {
if constexpr (N < std::tuple_size<T>::value) {
auto &x = std::get<N>(t);
rd(x);
rd_tuple<N + 1>(t);
}
}
template <class... T>
void rd(tuple<T...> &tpl) {
rd_tuple(tpl);
}
template <size_t N = 0, typename T>
void rd(array<T, N> &x) {
for (auto &d: x) rd(d);
}
template <class T>
void rd(vc<T> &x) {
for (auto &d: x) rd(d);
}
void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
rd(h), read(t...);
}
void wt(const char c) {
if (por == SZ) flush();
obuf[por++] = c;
}
void wt(const string s) {
for (char c: s) wt(c);
}
void wt(const char *s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; i++) wt(s[i]);
}
template <typename T>
void wt_integer(T x) {
if (por > SZ - 100) flush();
if (x < 0) { obuf[por++] = '-', x = -x; }
int outi;
for (outi = 96; x >= 10000; outi -= 4) {
memcpy(out + outi, pre.num[x % 10000], 4);
x /= 10000;
}
if (x >= 1000) {
memcpy(obuf + por, pre.num[x], 4);
por += 4;
} else if (x >= 100) {
memcpy(obuf + por, pre.num[x] + 1, 3);
por += 3;
} else if (x >= 10) {
int q = (x * 103) >> 10;
obuf[por] = q | '0';
obuf[por + 1] = (x - q * 10) | '0';
por += 2;
} else
obuf[por++] = x | '0';
memcpy(obuf + por, out + outi + 4, 96 - outi);
por += 96 - outi;
}
template <typename T>
void wt_real(T x) {
ostringstream oss;
oss << fixed << setprecision(15) << double(x);
string s = oss.str();
wt(s);
}
void wt(int x) { wt_integer(x); }
void wt(ll x) { wt_integer(x); }
void wt(i128 x) { wt_integer(x); }
void wt(u32 x) { wt_integer(x); }
void wt(u64 x) { wt_integer(x); }
void wt(u128 x) { wt_integer(x); }
void wt(double x) { wt_real(x); }
void wt(long double x) { wt_real(x); }
void wt(f128 x) { wt_real(x); }
template <class T, class U>
void wt(const pair<T, U> val) {
wt(val.first);
wt(' ');
wt(val.second);
}
template <size_t N = 0, typename T>
void wt_tuple(const T t) {
if constexpr (N < std::tuple_size<T>::value) {
if constexpr (N > 0) { wt(' '); }
const auto x = std::get<N>(t);
wt(x);
wt_tuple<N + 1>(t);
}
}
template <class... T>
void wt(tuple<T...> tpl) {
wt_tuple(tpl);
}
template <class T, size_t S>
void wt(const array<T, S> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) wt(' ');
wt(val[i]);
}
}
template <class T>
void wt(const vector<T> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) wt(' ');
wt(val[i]);
}
}
void print() { wt('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
wt(head);
if (sizeof...(Tail)) wt(' ');
print(forward<Tail>(tail)...);
}
// gcc expansion. called automaticall after main.
void __attribute__((destructor)) _d() { flush(); }
} // namespace fastio
using fastio::read;
using fastio::print;
using fastio::flush;
#if defined(LOCAL)
#define SHOW(...) SHOW_IMPL(__VA_ARGS__, SHOW6, SHOW5, SHOW4, SHOW3, SHOW2, SHOW1)(__VA_ARGS__)
#define SHOW_IMPL(_1, _2, _3, _4, _5, _6, NAME, ...) NAME
#define SHOW1(x) print(#x, "=", (x)), flush()
#define SHOW2(x, y) print(#x, "=", (x), #y, "=", (y)), flush()
#define SHOW3(x, y, z) print(#x, "=", (x), #y, "=", (y), #z, "=", (z)), flush()
#define SHOW4(x, y, z, w) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w)), flush()
#define SHOW5(x, y, z, w, v) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w), #v, "=", (v)), flush()
#define SHOW6(x, y, z, w, v, u) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w), #v, "=", (v), #u, "=", (u)), flush()
#else
#define SHOW(...)
#endif
#define INT(...) \
int __VA_ARGS__; \
read(__VA_ARGS__)
#define LL(...) \
ll __VA_ARGS__; \
read(__VA_ARGS__)
#define U32(...) \
u32 __VA_ARGS__; \
read(__VA_ARGS__)
#define U64(...) \
u64 __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"
#line 2 "/home/maspy/compro/library/geo/base.hpp"
template <typename T>
struct Point {
T x, y;
Point() : x(0), y(0) {}
template <typename A, typename B>
Point(A x, B y) : x(x), y(y) {}
template <typename A, typename B>
Point(pair<A, B> p) : x(p.fi), y(p.se) {}
Point operator+=(const Point p) {
x += p.x, y += p.y;
return *this;
}
Point operator-=(const Point p) {
x -= p.x, y -= p.y;
return *this;
}
Point operator+(Point p) const { return {x + p.x, y + p.y}; }
Point operator-(Point p) const { return {x - p.x, y - p.y}; }
bool operator==(Point p) const { return x == p.x && y == p.y; }
bool operator!=(Point p) const { return x != p.x || y != p.y; }
Point operator-() const { return {-x, -y}; }
Point operator*(T t) const { return {x * t, y * t}; }
Point operator/(T t) const { return {x / t, y / t}; }
bool operator<(Point p) const {
if (x != p.x) return x < p.x;
return y < p.y;
}
T dot(const Point& other) const { return x * other.x + y * other.y; }
T det(const Point& other) const { return x * other.y - y * other.x; }
double norm() { return sqrtl(x * x + y * y); }
double angle() { return atan2(y, x); }
Point rotate(double theta) {
static_assert(!is_integral<T>::value);
double c = cos(theta), s = sin(theta);
return Point{c * x - s * y, s * x + c * y};
}
Point rot90(bool ccw) { return (ccw ? Point{-y, x} : Point{y, -x}); }
};
#ifdef FASTIO
template <typename T>
void rd(Point<T>& p) {
fastio::rd(p.x), fastio::rd(p.y);
}
template <typename T>
void wt(Point<T>& p) {
fastio::wt(p.x);
fastio::wt(' ');
fastio::wt(p.y);
}
#endif
// A -> B -> C と進むときに、左に曲がるならば +1、右に曲がるならば -1
template <typename T>
int ccw(Point<T> A, Point<T> B, Point<T> C) {
T x = (B - A).det(C - A);
if (x > 0) return 1;
if (x < 0) return -1;
return 0;
}
template <typename REAL, typename T, typename U>
REAL dist(Point<T> A, Point<U> B) {
REAL dx = REAL(A.x) - REAL(B.x);
REAL dy = REAL(A.y) - REAL(B.y);
return sqrt(dx * dx + dy * dy);
}
// ax+by+c
template <typename T>
struct Line {
T a, b, c;
Line(T a, T b, T c) : a(a), b(b), c(c) {}
Line(Point<T> A, Point<T> B) { a = A.y - B.y, b = B.x - A.x, c = A.x * B.y - A.y * B.x; }
Line(T x1, T y1, T x2, T y2) : Line(Point<T>(x1, y1), Point<T>(x2, y2)) {}
template <typename U>
U eval(Point<U> P) {
return a * P.x + b * P.y + c;
}
template <typename U>
T eval(U x, U y) {
return a * x + b * y + c;
}
// 同じ直線が同じ a,b,c で表現されるようにする
void normalize() {
static_assert(is_same_v<T, int> || is_same_v<T, long long>);
T g = gcd(gcd(abs(a), abs(b)), abs(c));
a /= g, b /= g, c /= g;
if (b < 0) { a = -a, b = -b, c = -c; }
if (b == 0 && a < 0) { a = -a, b = -b, c = -c; }
}
bool is_parallel(Line other) { return a * other.b - b * other.a == 0; }
bool is_orthogonal(Line other) { return a * other.a + b * other.b == 0; }
};
template <typename T>
struct Segment {
Point<T> A, B;
Segment(Point<T> A, Point<T> B) : A(A), B(B) {}
Segment(T x1, T y1, T x2, T y2) : Segment(Point<T>(x1, y1), Point<T>(x2, y2)) {}
bool contain(Point<T> C) {
T det = (C - A).det(B - A);
if (det != 0) return 0;
return (C - A).dot(B - A) >= 0 && (C - B).dot(A - B) >= 0;
}
Line<T> to_Line() { return Line(A, B); }
};
template <typename REAL>
struct Circle {
Point<REAL> O;
REAL r;
Circle(Point<REAL> O, REAL r) : O(O), r(r) {}
Circle(REAL x, REAL y, REAL r) : O(x, y), r(r) {}
template <typename T>
bool contain(Point<T> p) {
REAL dx = p.x - O.x, dy = p.y - O.y;
return dx * dx + dy * dy <= r * r;
}
};
#line 2 "/home/maspy/compro/library/geo/cross_point.hpp"
#line 4 "/home/maspy/compro/library/geo/cross_point.hpp"
// 平行でないことを仮定
template <typename REAL, typename T>
Point<REAL> cross_point(const Line<T> L1, const Line<T> L2) {
T det = L1.a * L2.b - L1.b * L2.a;
assert(det != 0);
REAL x = -REAL(L1.c) * L2.b + REAL(L1.b) * L2.c;
REAL y = -REAL(L1.a) * L2.c + REAL(L1.c) * L2.a;
return Point<REAL>(x / det, y / det);
}
// 浮動小数点数はエラー
// 0: 交点なし
// 1: 一意な交点
// 2:2 つ以上の交点(整数型を利用して厳密にやる)
template <typename T>
int count_cross(Segment<T> S1, Segment<T> S2, bool include_ends) {
static_assert(!std::is_floating_point<T>::value);
Line<T> L1 = S1.to_Line();
Line<T> L2 = S2.to_Line();
if (L1.is_parallel(L2)) {
if (L1.eval(S2.A) != 0) return 0;
// 4 点とも同一直線上にある
T a1 = S1.A.x, b1 = S1.B.x;
T a2 = S2.A.x, b2 = S2.B.x;
if (a1 == b1) {
a1 = S1.A.y, b1 = S1.B.y;
a2 = S2.A.y, b2 = S2.B.y;
}
if (a1 > b1) swap(a1, b1);
if (a2 > b2) swap(a2, b2);
T a = max(a1, a2);
T b = min(b1, b2);
if (a < b) return 2;
if (a > b) return 0;
return (include_ends ? 1 : 0);
}
// 平行でない場合
T a1 = L2.eval(S1.A), b1 = L2.eval(S1.B);
T a2 = L1.eval(S2.A), b2 = L1.eval(S2.B);
if (a1 > b1) swap(a1, b1);
if (a2 > b2) swap(a2, b2);
bool ok1 = 0, ok2 = 0;
if (include_ends) {
ok1 = (a1 <= T(0)) && (T(0) <= b1);
ok2 = (a2 <= T(0)) && (T(0) <= b2);
} else {
ok1 = (a1 < T(0)) && (T(0) < b1);
ok2 = (a2 < T(0)) && (T(0) < b2);
}
return (ok1 && ok2 ? 1 : 0);
}
// https://codeforces.com/contest/607/problem/E
template <typename REAL, typename T>
vc<Point<REAL>> cross_point(const Circle<T> C, const Line<T> L) {
T a = L.a, b = L.b, c = L.a * (C.O.x) + L.b * (C.O.y) + L.c;
T r = C.r;
bool SW = 0;
if (abs(a) < abs(b)) {
swap(a, b);
SW = 1;
}
// ax+by+c=0, x^2+y^2=r^2
T D = 4 * c * c * b * b - 4 * (a * a + b * b) * (c * c - a * a * r * r);
if (D < 0) return {};
REAL sqD = sqrtl(D);
REAL y1 = (-2 * b * c + sqD) / (2 * (a * a + b * b));
REAL y2 = (-2 * b * c - sqD) / (2 * (a * a + b * b));
REAL x1 = (-b * y1 - c) / a;
REAL x2 = (-b * y2 - c) / a;
if (SW) swap(x1, y1), swap(x2, y2);
x1 += C.O.x, x2 += C.O.x;
y1 += C.O.y, y2 += C.O.y;
if (D == 0) return {Point<REAL>(x1, y1)};
return {Point<REAL>(x1, y1), Point<REAL>(x2, y2)};
}
// https://codeforces.com/contest/2/problem/C
template <typename REAL, typename T>
tuple<bool, Point<T>, Point<T>> cross_point_circle(Circle<T> C1, Circle<T> C2) {
using P = Point<T>;
P O{0, 0};
P A = C1.O, B = C2.O;
if (A == B) return {false, O, O};
T d = (B - A).norm();
REAL cos_val = (C1.r * C1.r + d * d - C2.r * C2.r) / (2 * C1.r * d);
if (cos_val < -1 || 1 < cos_val) return {false, O, O};
REAL t = acos(cos_val);
REAL u = (B - A).angle();
P X = A + P{C1.r * cos(u + t), C1.r * sin(u + t)};
P Y = A + P{C1.r * cos(u - t), C1.r * sin(u - t)};
return {true, X, Y};
}
#line 3 "/home/maspy/compro/library/geo/polygon.hpp"
template <typename T>
struct Polygon {
vc<Point<T>> point;
T a;
Polygon(vc<Point<T>> point) : point(point) { build(); }
int size() { return len(point); }
template <typename REAL>
REAL area() {
return a * 0.5;
}
T area_2() { return a; }
bool is_convex() {
FOR(j, len(point)) {
int i = (j == 0 ? len(point) - 1 : j - 1);
int k = (j == len(point) - 1 ? 0 : j + 1);
if ((point[j] - point[i]).det(point[k] - point[j]) < 0) return false;
}
return true;
}
// 中:1, 境界:0, 外:-1.
int side(Point<T> p) {
int n = len(point);
FOR(i, n) if (point[i] == p) return 0;
FOR(i, n) {
Point<T> A = point[i], B = point[(i + 1) % n];
if ((p - A).det(B - A) != 0) continue;
if ((p - A).dot(B - A) >= 0 && (p - B).dot(A - B) >= 0) return 0;
}
// p から x 方向に (+1, +eps) 方向にのびる半直線との交差を考える
int cnt = 0;
FOR(i, n) {
Point<T> A = point[i], B = point[(i + 1) % n];
FOR(2) {
swap(A, B);
if (A.y > p.y) continue;
if (B.y <= p.y) continue;
if ((A - p).det(B - p) > 0) ++cnt;
}
}
return (cnt % 2 == 0 ? -1 : 1);
}
// point[i] の近傍だけで見た side
// https://github.com/maspypy/library/blob/main/geo/polygon_side.png
int side_at(int i, Point<T> p) {
int n = len(point);
p -= point[i];
if (p.x == T(0) && p.y == T(0)) return 0;
Point<T> L = point[(i + 1) % n] - point[i];
Point<T> R = point[(i + n - 1) % n] - point[i];
auto sgn = [&](T x) -> int {
if (x == T(0)) return 0;
return (x > T(0) ? 1 : -1);
};
int x = sgn(L.det(p)) + sgn(p.det(R)) + sgn(R.det(L));
if (x == 0) return x;
return (x > 0 ? 1 : -1);
}
// 線分が内部・外部それぞれを通るか
// https://atcoder.jp/contests/jag2016-domestic/tasks/jag2016secretspring_e
// https://atcoder.jp/contests/JAG2014Spring/tasks/icpc2014spring_f
pair<bool, bool> side_segment(Point<T> L, Point<T> R) {
Segment<T> S(L, R);
// まず線分と非自明に交わるパターン
int n = len(point);
FOR(i, n) {
Segment<T> S2(point[i], point[(i + 1) % n]);
if (count_cross(S, S2, false) == 1) { return {1, 1}; }
}
bool in = 0, out = 0;
if (side(L) == 1 || side(R) == 1) in = 1;
if (side(L) == -1 || side(R) == -1) out = 1;
FOR(i, n) {
if (!S.contain(point[i])) continue;
for (auto& p: {L, R}) {
int k = side_at(i, p);
if (k == 1) in = 1;
if (k == -1) out = 1;
}
}
return {in, out};
}
private:
void build() {
a = 0;
FOR(i, len(point)) {
int j = (i + 1 == len(point) ? 0 : i + 1);
a += point[i].det(point[j]);
}
assert(a > 0);
}
};
#line 7 "main.cpp"
/*
・辺に三角形をくっつける OR 凹な2辺に三角形をくつける
・ちょうど180度になった頂点を「消す」
くっつけるのは三角形だけでよさそう
順列順につけるだけだとだめです
*/
using Re = long double;
using P = Point<Re>;
// ???
const Re eps = 1e-7;
struct T {
vc<P> point;
vi edge_len;
int size() { return len(point); }
void rot() {
rotate(point.begin(), point.begin() + 1, point.end());
rotate(edge_len.begin(), edge_len.begin() + 1, edge_len.end());
}
void flip() {
reverse(all(edge_len));
// 0,1,2,3,4 -> 0,4,3,2,1
reverse(point.begin() + 1, point.end());
for (auto& p: point) p.y = -p.y;
}
void check() {
int n = len(point);
FOR(i, n) SHOW(point[i]);
FOR(i, n) {
P A = point[i];
P B = point[(i + 1) % n];
Re d = (B - A).dot(B - A);
SHOW(d, edge_len[i]);
assert(abs(d - edge_len[i]) < eps);
}
}
};
pair<bool, P> add_point(P A, P B, ll a, ll b) {
// A から距離 a, B から距離 b, AB からみて右手側
Circle<Re> C1(A, sqrtl(a));
Circle<Re> C2(B, sqrtl(b));
auto [ok, P, Q] = cross_point_circle<Re, Re>(C1, C2);
if (!ok) return {false, A};
FOR(2) {
swap(P, Q);
Re det = (P - A).det(B - A);
if (det <= eps) continue;
return {true, P};
}
return {false, A};
}
pair<bool, T> remove_extra(T t) {
// 180度の頂点を削除
int N = len(t);
FOR(2 * N) {
int n = len(t);
t.rot();
P A = t.point[0];
P B = t.point[1];
P C = t.point[2];
Re det = (B - A).det(C - A);
if (abs(det) > eps) continue;
// B を削除??
Re dot = (A - C).dot(A - C);
ll c = round(dot);
if (abs(c - dot) > eps) return {false, t};
T u;
FOR(i, n) if (i != 1) u.point.eb(t.point[i]);
u.edge_len.eb(c);
FOR(i, 2, n) u.edge_len.eb(t.edge_len[i]);
swap(t, u);
}
return {true, t};
}
bool check_square(T t) {
int n = len(t);
if (n != 4) return 0;
if (MIN(t.edge_len) != MAX(t.edge_len)) return 0;
FOR(i, 4) SHOW(i, t.point[i].x, t.point[i].y);
SHOW(t.edge_len);
// ひしがた
P AB = t.point[1] - t.point[0];
P BC = t.point[2] - t.point[1];
Re dot = AB.dot(BC);
return abs(dot) < eps;
}
bool dfs(vc<T> dat) {
int K = len(dat);
if (K == 1) return check_square(dat[0]);
auto last_two = [&](vc<T> dat) -> bool {
T R = POP(dat);
T L = POP(dat);
int N = len(L), M = len(R);
if (M != 3) return 0;
vi S = R.edge_len;
sort(all(S));
do {
ll a = S[0], b = S[1], c = S[2];
// 辺の外部にくっつけるパターン
FOR(N) {
L.rot();
if (L.edge_len[1] != c) continue;
P A = L.point[0], B = L.point[1];
P C = L.point[2], D = L.point[3 % N];
// L[1]->L[2] のところに
auto [ok, p] = add_point(B, C, a, b);
if (!ok) continue;
/*
雑チェック!
まわりの辺との位置関係が大丈夫か?
*/
Polygon<Re> poly(L.point);
if (poly.side_at(1, p) == 1) continue;
if (poly.side_at(2, p) == 1) continue;
T nxt;
FOR(i, 2) nxt.point.eb(L.point[i]);
nxt.point.eb(p);
FOR(i, 2, N) nxt.point.eb(L.point[i]);
nxt.edge_len.eb(L.edge_len[0]);
nxt.edge_len.eb(a);
nxt.edge_len.eb(b);
FOR(i, 2, N) nxt.edge_len.eb(L.edge_len[i]);
tie(ok, nxt) = remove_extra(nxt);
if (!ok) continue;
dat.eb(nxt);
if (dfs(dat)) return 1;
POP(dat);
}
// 2辺にはり合わせるパターン
FOR(N) {
L.rot();
if (L.edge_len[1] != c) continue;
P A = L.point[0], B = L.point[1], C = L.point[2];
if (ccw(A, B, C) != -1) continue;
if (L.edge_len[0] != a) continue;
if (L.edge_len[1] != b) continue;
Re x = (A - C).norm();
if (abs(x - sqrtl(c)) > eps) continue;
// 置き換え可能だとわかった
T nxt;
FOR(i, N) if (i != 1) nxt.point.eb(L.point[i]);
nxt.edge_len.eb(c);
FOR(i, 2, N) nxt.edge_len.eb(L.edge_len[i]);
bool ok = 0;
tie(ok, nxt) = remove_extra(nxt);
if (!ok) continue;
dat.eb(nxt);
if (dfs(dat)) return 1;
POP(dat);
}
} while (next_permutation(all(S)));
return 0;
};
FOR(K) {
rotate(dat.begin(), dat.begin() + 1, dat.end());
FOR(K - 1) {
rotate(dat.begin(), dat.begin() + 1, dat.end() - 1);
FOR(2) {
dat.back().flip();
if (last_two(dat)) return true;
}
}
}
return false;
}
void solve() {
vc<T> init;
FOR(4) {
LL(a, b, c);
P A(0, 0);
P B(sqrtl(c), 0);
auto [ok, C] = add_point(A, B, a, b);
assert(ok);
T t;
t.point = {B, A, C};
t.edge_len = {c, a, b};
init.eb(t);
}
FOR(i, 4) init[i].check();
print(dfs(init));
}
signed main() {
INT(T);
FOR(T) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 14ms
memory: 3752kb
input:
3 1 1 2 2 1 1 2 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 5 125 130 125 20 145 45 130 145 145 145 80
output:
1 0 1
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 511ms
memory: 3628kb
input:
20 1998001 7984010 9982009 1998001 7984010 1994005 7984010 9978013 9982009 9978013 1994005 7984010 9958045 7968034 9962037 7968034 1994005 9962037 9958045 1990013 7968034 1994005 1990013 7968034 7952074 9938097 1986025 7952074 9942085 1990013 7952074 9942085 9938097 1986025 7952074 1990013 7936130 9...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
wrong answer 1st lines differ - expected: '1', found: '0'