QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#298376 | #7903. Computational Intelligence | ucup-team987 | WA | 0ms | 4308kb | C++23 | 8.9kb | 2024-01-06 04:42:11 | 2024-01-06 04:42:12 |
Judging History
answer
#if __INCLUDE_LEVEL__ == 0
#include __BASE_FILE__
namespace {
using kactl::P;
double F(double x, double b) {
if (b == 0) {
x = std::abs(x);
return x * x * x / 6;
}
double ret = x * std::log(std::sqrt(x * x + b * b) + x) - std::sqrt(x * x + b * b);
ret *= b * b;
ret += std::pow(x * x + b * b, 1.5) / 3;
ret /= 2;
return ret;
}
double solve(double a, double b) { return F(-a, b) - F(1 - a, b); }
double solve(P B) {
if (B.y < 0) {
B.y = -B.y;
return -solve(B);
}
const double a = B.x;
const double c = B.dist();
const double X = c * c * c / 3 * B.angle();
const auto f = [&](double r) {
double ret = 0;
ret += r * r * r / 3 * std::acos(a / r);
const double t = std::sqrt(1 - (a * a) / (r * r));
ret -= (r * r * t + a * a * std::log(r * (t + 1))) * a / 6;
return ret;
};
const double Y = f(c) - f(a);
return X - Y;
}
double solve(P A, P B) {
{
const double t = std::numbers::pi / 2 - (B - A).angle();
A = A.rotate(t);
B = B.rotate(t);
}
return solve(B) - solve(A);
}
double solve(P p1, P p2, P p3, P p4) {
if ((p2 - p1).cross(p4 - p3) == 0) {
p3 = kactl::linearTransformation(p1, p2, P(0, 0), P(1, 0), p3);
p4 = kactl::linearTransformation(p1, p2, P(0, 0), P(1, 0), p4);
assert(p3.y == p4.y);
if (p3.y < 0) {
p3.y = -p3.y;
p4.y = -p4.y;
}
if (p4.x < p3.x) {
std::swap(p3, p4);
}
double ans = solve(p4.x, p3.y) - solve(p3.x, p3.y);
ans /= p4.x - p3.x;
ans *= (p2 - p1).dist();
return ans;
} else {
auto hull = kactl::convexHull({p3 - p1, p4 - p1, p3 - p2, p4 - p2});
assert(len(hull) == 4);
hull.push_back(hull[0]);
double ans = 0;
double area = 0;
for (const int i : rep(4)) {
const double cross = hull[i].cross(hull[i + 1]);
if (0 < cross) {
ans += solve(hull[i], hull[i + 1]);
} else if (cross < 0) {
ans -= solve(hull[i + 1], hull[i]);
}
area += cross;
}
area /= 2;
ans /= area;
return ans;
}
}
void solve() {
P p1, p2;
scan(p1.x, p1.y, p2.x, p2.y);
P p3, p4;
scan(p3.x, p3.y, p4.x, p4.y);
std::cout << std::setprecision(DBL_DIG);
print(solve(p1, p2, p3, p4));
}
} // namespace
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
scan(t);
while (t--) {
solve();
}
}
#else // __INCLUDE_LEVEL__
#include <bits/stdc++.h>
// https://github.com/kth-competitive-programming/kactl
namespace kactl {
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template <class T>
int sgn(T x) {
return (x > 0) - (x < 0);
}
template <class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x = 0, T y = 0) : x(x), y(y) {}
bool operator<(P p) const { return tie(x, y) < tie(p.x, p.y); }
bool operator==(P p) const { return tie(x, y) == tie(p.x, p.y); }
P operator+(P p) const { return P(x + p.x, y + p.y); }
P operator-(P p) const { return P(x - p.x, y - p.y); }
P operator*(T d) const { return P(x * d, y * d); }
P operator/(T d) const { return P(x / d, y / d); }
T dot(P p) const { return x * p.x + y * p.y; }
T cross(P p) const { return x * p.y - y * p.x; }
T cross(P a, P b) const { return (a - *this).cross(b - *this); }
T dist2() const { return x * x + y * y; }
double dist() const { return sqrt((double)dist2()); }
double angle() const { return atan2(y, x); }
P unit() const { return *this / dist(); }
P perp() const { return P(-y, x); }
P normal() const { return perp().unit(); }
P rotate(double a) const { return P(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a)); }
friend ostream& operator<<(ostream& os, P p) { return os << "(" << p.x << "," << p.y << ")"; }
};
typedef Point<double> P;
vector<P> convexHull(vector<P> pts) {
if (sz(pts) <= 1) return pts;
sort(all(pts));
vector<P> h(sz(pts) + 1);
int s = 0, t = 0;
for (int it = 2; it--; s = --t, reverse(all(pts)))
for (P p : pts) {
while (t >= s + 2 && h[t - 2].cross(h[t - 1], p) <= 0) t--;
h[t++] = p;
}
return {h.begin(), h.begin() + t - (t == 2 && h[0] == h[1])};
}
typedef Point<double> P;
P linearTransformation(const P& p0, const P& p1, const P& q0, const P& q1, const P& r) {
P dp = p1 - p0, dq = q1 - q0, num(dp.cross(dq), dp.dot(dq));
return q0 + P((r - p0).cross(num), (r - p0).dot(num)) / dp.dist2();
}
#undef sz
#undef all
} // namespace kactl
template <class T, class U = T>
bool chmin(T& x, U&& y) {
return y < x && (x = std::forward<U>(y), true);
}
template <class T, class U = T>
bool chmax(T& x, U&& y) {
return x < y && (x = std::forward<U>(y), true);
}
template <class T>
concept Range = std::ranges::range<T> && !std::convertible_to<T, std::string_view>;
template <class T>
concept TupleLike = std::__is_tuple_like<T>::value && !Range<T>;
namespace std {
istream& operator>>(istream& is, Range auto&& r) {
for (auto&& e : r) {
is >> e;
}
return is;
}
istream& operator>>(istream& is, TupleLike auto&& t) {
return apply([&](auto&... xs) -> istream& { return (is >> ... >> xs); }, t);
}
ostream& operator<<(ostream& os, Range auto&& r) {
string_view sep = "";
for (auto&& e : r) {
os << exchange(sep, " ") << e;
}
return os;
}
ostream& operator<<(ostream& os, TupleLike auto&& t) {
const auto f = [&](auto&... xs) -> ostream& {
[[maybe_unused]] string_view sep = "";
((os << exchange(sep, " ") << xs), ...);
return os;
};
return apply(f, t);
}
#define DEF_INC_OR_DEC(op) \
auto& operator op(Range auto&& r) { \
for (auto&& e : r) { \
op e; \
} \
return r; \
} \
auto& operator op(TupleLike auto&& t) { \
apply([](auto&... xs) { (op xs, ...); }, t); \
return t; \
}
DEF_INC_OR_DEC(++)
DEF_INC_OR_DEC(--)
#undef DEF_INC_OR_DEC
} // namespace std
void scan(auto&&... xs) { std::cin >> std::tie(xs...); }
void print(auto&&... xs) { std::cout << std::tie(xs...) << '\n'; }
#define FWD(...) static_cast<decltype(__VA_ARGS__)&&>(__VA_ARGS__)
template <class F>
class fix {
public:
explicit fix(F f) : f_(std::move(f)) {}
decltype(auto) operator()(auto&&... xs) const { return f_(std::ref(*this), FWD(xs)...); }
private:
F f_;
};
template <class T>
concept LambdaExpr = std::is_placeholder_v<std::remove_cvref_t<T>> != 0 ||
std::is_bind_expression_v<std::remove_cvref_t<T>>;
auto operator++(LambdaExpr auto&& x, int) {
return std::bind([](auto&& x) -> decltype(auto) { return FWD(x)++; }, FWD(x));
}
auto operator--(LambdaExpr auto&& x, int) {
return std::bind([](auto&& x) -> decltype(auto) { return FWD(x)--; }, FWD(x));
}
#define DEF_UNARY_OP(op) \
auto operator op(LambdaExpr auto&& x) { \
return std::bind([](auto&& x) -> decltype(auto) { return op FWD(x); }, FWD(x)); \
}
DEF_UNARY_OP(++)
DEF_UNARY_OP(--)
DEF_UNARY_OP(+)
DEF_UNARY_OP(-)
DEF_UNARY_OP(~)
DEF_UNARY_OP(!)
DEF_UNARY_OP(*)
DEF_UNARY_OP(&)
#undef DEF_UNARY_OP
#define DEF_BINARY_OP(op) \
template <class T1, class T2> \
requires LambdaExpr<T1> || LambdaExpr<T2> \
auto operator op(T1&& x, T2&& y) { \
return std::bind([](auto&& x, auto&& y) -> decltype(auto) { return FWD(x) op FWD(y); }, \
FWD(x), FWD(y)); \
}
DEF_BINARY_OP(+=)
DEF_BINARY_OP(-=)
DEF_BINARY_OP(*=)
DEF_BINARY_OP(/=)
DEF_BINARY_OP(%=)
DEF_BINARY_OP(^=)
DEF_BINARY_OP(&=)
DEF_BINARY_OP(|=)
DEF_BINARY_OP(<<=)
DEF_BINARY_OP(>>=)
DEF_BINARY_OP(+)
DEF_BINARY_OP(-)
DEF_BINARY_OP(*)
DEF_BINARY_OP(/)
DEF_BINARY_OP(%)
DEF_BINARY_OP(^)
DEF_BINARY_OP(&)
DEF_BINARY_OP(|)
DEF_BINARY_OP(<<)
DEF_BINARY_OP(>>)
DEF_BINARY_OP(==)
DEF_BINARY_OP(!=)
DEF_BINARY_OP(<)
DEF_BINARY_OP(>)
DEF_BINARY_OP(<=)
DEF_BINARY_OP(>=)
DEF_BINARY_OP(&&)
DEF_BINARY_OP(||)
#undef DEF_BINARY_OP
template <class T1, class T2>
requires LambdaExpr<T1> || LambdaExpr<T2>
auto at(T1&& x, T2&& y) {
return std::bind([](auto&& x, auto&& y) -> decltype(auto) { return FWD(x)[FWD(y)]; }, FWD(x),
FWD(y));
}
template <int I>
auto get(LambdaExpr auto&& x) {
return std::bind([](auto&& x) -> decltype(auto) { return std::get<I>(FWD(x)); }, FWD(x));
}
inline auto rep(int l, int r) { return std::views::iota(std::min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
#define len(...) static_cast<int>(ranges::distance(__VA_ARGS__))
using namespace std::literals;
using namespace std::placeholders;
namespace ranges = std::ranges;
namespace views = std::views;
using i64 = std::int64_t;
#endif // __INCLUDE_LEVEL__
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4272kb
input:
3 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 1 1
output:
0.333333333333333 0.765195716464212 1.07663573289518
result:
ok 3 numbers
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 4308kb
input:
3 0 1 0 0 0 -1 0 2 0 0 1 0 2 0 -1 0 -1000 0 0 999 0 -998 999 0
output:
0.777777777777778 0.777777777777778 1521.0706820488
result:
wrong answer 3rd numbers differ - expected: '1521.0704050', found: '1521.0706820', error = '0.0000002'