QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#805389 | #9869. Horizon Scanning | jayket | AC ✓ | 62ms | 6092kb | C++23 | 21.0kb | 2024-12-08 16:24:28 | 2024-12-08 16:24:35 |
Judging History
answer
#include<bits/stdc++.h>
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using f64 = long double;
using i128 = __int128;
using u128 = unsigned __int128;
using f128 = __float128;
#ifndef ONLINE_JUDGE
#include "algo/debug.hpp"
#else
#define debug(...) (void)42
#endif
template<class T>
constexpr bool chmax(T& x, T y) {
if (y > x) {
x = y;
return true;
}
return false;
}
template<class T>
constexpr bool chmin(T& x, T y) {
if (y < x) {
x = y;
return true;
}
return false;
}
template<class T>
struct Point {
T x;
T y;
Point(const T &x_ = 0, const T &y_ = 0) : x(x_), y(y_) {}
template<class U>
operator Point<U>() {
return Point<U>(U(x), U(y));
}
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*=(const T &v) & {
x *= v;
y *= v;
return *this;
}
Point &operator/=(const T &v) & {
x /= v;
y /= v;
return *this;
}
Point operator-() const {
return Point(-x, -y);
}
constexpr friend Point operator+(Point a, const Point &b) {
return a += b;
}
constexpr friend Point operator-(Point a, const Point &b) {
return a -= b;
}
constexpr friend Point operator*(Point a, const T &b) {
return a *= b;
}
constexpr friend Point operator/(Point a, const T &b) {
return a /= b;
}
constexpr friend Point operator*(const T &a, Point b) {
return b *= a;
}
constexpr friend bool operator==(const Point &a, const Point &b) {
return a.x == b.x && a.y == b.y;
}
constexpr friend bool operator<(const Point& a, const Point& b) {
return (a.x == b.x) ? a.y < b.y : a.x < b.x;
}
friend std::istream &operator>>(std::istream &is, Point &p) {
return is >> p.x >> p.y;
}
friend std::ostream &operator<<(std::ostream &os, const Point &p) {
return os << "(" << p.x << ", " << p.y << ")";
}
};
template<class T>
struct Line {
Point<T> a;
Point<T> b;
Line(const Point<T> &a_ = Point<T>(), const Point<T> &b_ = Point<T>()) : a(a_), b(b_) {}
};
template<class T>
T dot(const Point<T> &a, const Point<T> &b) {
return a.x * b.x + a.y * b.y;
}
template<class T>
T cross(const Point<T> &a, const Point<T> &b) {
return a.x * b.y - a.y * b.x;
}
template<class T>
T square(const Point<T> &p) {
return dot(p, p);
}
template<class T>
f64 length(const Point<T> &p) {
return sqrtl(square(p));
}
template<class T>
f64 length(const Line<T> &l) {
return length(l.a - l.b);
}
template<class T>
Point<T> normalize(const Point<T> &p) {
return p / length(p);
}
template<class T>
bool parallel(const Line<T> &l1, const Line<T> &l2) {
return cross(l1.b - l1.a, l2.b - l2.a) == 0;
}
template<class T>
f64 distance(const Point<T> &a, const Point<T> &b) {
return length(a - b);
}
template<class T>
f64 distancePL(const Point<T> &p, const Line<T> &l) {
return std::abs(cross(l.a - l.b, l.a - p)) / length(l);
}
template<class T>
f64 distancePS(const Point<T> &p, const Line<T> &l) {
if (dot(p - l.a, l.b - l.a) < 0) {
return distance(p, l.a);
}
if (dot(p - l.b, l.a - l.b) < 0) {
return distance(p, l.b);
}
return distancePL(p, l);
}
template<class T>
Point<T> rotate(const Point<T> &a) {
return Point(-a.y, a.x);
}
template<class T>
int sgn(const Point<T> &a) {
return a.y > 0 or (a.y == 0 and a.x > 0) ? 1 : -1;
}
template<class T>
bool compute(const Point<T>& a, const Point<T>& b) {
if (sgn(a) == sgn(b)) {
return cross(a, b) > 0;
}
return sgn(a) > sgn(b);
}
template<class T>
f64 angle(const Point<T>& p) {
return std::atan2<f64>(p.y, p.x);
}
template<class T>
f64 angle(const Line<T>& l) {
return angle(l.b - l.a);
}
template<class T>
bool pointOnLineLeft(const Point<T> &p, const Line<T> &l) {
return cross(l.b - l.a, p - l.a) > 0;
}
template<class T>
Point<T> lineIntersection(const Line<T> &l1, const Line<T> &l2) {
return l1.a + (l1.b - l1.a) * (cross(l2.b - l2.a, l1.a - l2.a) / cross(l2.b - l2.a, l1.a - l1.b));
}
template<class T>
bool pointOnSegment(const Point<T> &p, const Line<T> &l) {
return cross(p - l.a, l.b - l.a) == 0 and std::min(l.a.x, l.b.x) <= p.x and p.x <= std::max(l.a.x, l.b.x) and std::min(l.a.y, l.b.y) <= p.y and p.y <= std::max(l.a.y, l.b.y);
}
template<class T>
bool pointOnLine(const Point<T> &p, const Line<T> &l) {
return pointOnSegment(p, l) or pointOnSegment(l.a, Line(p, l.b)) or pointOnSegment(l.b, Line(p, l.a));
}
template<class T>
bool pointInPolygon(const Point<T> &a, const std::vector<Point<T>> &p) {
int n = p.size();
for (int i = 0; i < n; i++) {
if (pointOnSegment(a, Line(p[i], p[(i + 1) % n]))) {
return true;
}
}
int t = 0;
for (int i = 0; i < n; i++) {
const auto &u = p[i];
const auto &v = p[(i + 1) % n];
if (u.x < a.x and v.x >= a.x and pointOnLineLeft(a, Line(v, u))) {
t ^= 1;
}
if (u.x >= a.x and v.x < a.x and pointOnLineLeft(a, Line(u, v))) {
t ^= 1;
}
}
return t == 1;
}
// 0 : not intersect
// 1 : strictly intersect
// 2 : overlap
// 3 : intersect at endpoint
template<class T>
std::tuple<int, Point<T>, Point<T>> segmentIntersection(const Line<T> &l1, const Line<T> &l2) {
if (std::max(l1.a.x, l1.b.x) < std::min(l2.a.x, l2.b.x)) {
return {0, Point<T>(), Point<T>()};
}
if (std::min(l1.a.x, l1.b.x) > std::max(l2.a.x, l2.b.x)) {
return {0, Point<T>(), Point<T>()};
}
if (std::max(l1.a.y, l1.b.y) < std::min(l2.a.y, l2.b.y)) {
return {0, Point<T>(), Point<T>()};
}
if (std::min(l1.a.y, l1.b.y) > std::max(l2.a.y, l2.b.y)) {
return {0, Point<T>(), Point<T>()};
}
if (cross(l1.b - l1.a, l2.b - l2.a) == 0) {
if (cross(l1.b - l1.a, l2.a - l1.a) != 0) {
return {0, Point<T>(), Point<T>()};
} else {
const auto &maxx1 = std::max(l1.a.x, l1.b.x);
const auto &minx1 = std::min(l1.a.x, l1.b.x);
const auto &maxy1 = std::max(l1.a.y, l1.b.y);
const auto &miny1 = std::min(l1.a.y, l1.b.y);
const auto &maxx2 = std::max(l2.a.x, l2.b.x);
const auto &minx2 = std::min(l2.a.x, l2.b.x);
const auto &maxy2 = std::max(l2.a.y, l2.b.y);
const auto &miny2 = std::min(l2.a.y, l2.b.y);
Point<T> p1(std::max(minx1, minx2), std::max(miny1, miny2));
Point<T> p2(std::min(maxx1, maxx2), std::min(maxy1, maxy2));
if (!pointOnSegment(p1, l1)) {
std::swap(p1.y, p2.y);
}
if (p1 == p2) {
return {3, p1, p2};
} else {
return {2, p1, p2};
}
}
}
const auto &cp1 = cross(l2.a - l1.a, l2.b - l1.a);
const auto &cp2 = cross(l2.a - l1.b, l2.b - l1.b);
const auto &cp3 = cross(l1.a - l2.a, l1.b - l2.a);
const auto &cp4 = cross(l1.a - l2.b, l1.b - l2.b);
if ((cp1 > 0 and cp2 > 0) or (cp1 < 0 and cp2 < 0) or (cp3 > 0 and cp4 > 0) or (cp3 < 0 and cp4 < 0)) {
return {0, Point<T>(), Point<T>()};
}
Point p = lineIntersection(l1, l2);
if (cp1 != 0 and cp2 != 0 and cp3 != 0 and cp4 != 0) {
return {1, p, p};
} else {
return {3, p, p};
}
}
template<class T>
f64 distanceSS(const Line<T> &l1, const Line<T> &l2) {
if (std::get<0>(segmentIntersection(l1, l2)) != 0) {
return 0.0;
}
return std::min({distancePS(l1.a, l2), distancePS(l1.b, l2), distancePS(l2.a, l1), distancePS(l2.b, l1)});
}
template<class T>
bool segmentInPolygon(const Line<T> &l, const std::vector<Point<T>> &p) {
int n = p.size();
if (!pointInPolygon(l.a, p)) {
return false;
}
if (!pointInPolygon(l.b, p)) {
return false;
}
for (int i = 0; i < n; i++) {
const auto &u = p[i];
const auto &v = p[(i + 1) % n];
const auto &w = p[(i + 2) % n];
const auto &[t, p1, p2] = segmentIntersection(l, Line(u, v));
if (t == 1) {
return false;
}
if (t == 0) {
continue;
}
if (t == 2) {
if (pointOnSegment(v, l) and v != l.a and v != l.b) {
if (cross(v - u, w - v) > 0) {
return false;
}
}
} else {
if (p1 != u and p1 != v) {
if (pointOnLineLeft(l.a, Line(v, u)) or pointOnLineLeft(l.b, Line(v, u))) {
return false;
}
} else if (p1 == v) {
if (l.a == v) {
if (pointOnLineLeft(u, l)) {
if (pointOnLineLeft(w, l) and pointOnLineLeft(w, Line(u, v))) {
return false;
}
} else {
if (pointOnLineLeft(w, l) or pointOnLineLeft(w, Line(u, v))) {
return false;
}
}
} else if (l.b == v) {
if (pointOnLineLeft(u, Line(l.b, l.a))) {
if (pointOnLineLeft(w, Line(l.b, l.a)) and pointOnLineLeft(w, Line(u, v))) {
return false;
}
} else {
if (pointOnLineLeft(w, Line(l.b, l.a)) or pointOnLineLeft(w, Line(u, v))) {
return false;
}
}
} else {
if (pointOnLineLeft(u, l)) {
if (pointOnLineLeft(w, Line(l.b, l.a)) or pointOnLineLeft(w, Line(u, v))) {
return false;
}
} else {
if (pointOnLineLeft(w, l) or pointOnLineLeft(w, Line(u, v))) {
return false;
}
}
}
}
}
}
return true;
}
template<class T>
std::vector<Point<T>> hp(std::vector<Line<T>> lines) {
std::sort(lines.begin(), lines.end(), [&](const auto & l1, const auto & l2) {
const auto &d1 = l1.b - l1.a;
const auto &d2 = l2.b - l2.a;
if (sgn(d1) != sgn(d2)) {
return sgn(d1) == 1;
}
return cross(d1, d2) > 0;
});
std::deque<Line<T>> ls;
std::deque<Point<T>> ps;
for (const auto &l : lines) {
if (ls.empty()) {
ls.push_back(l);
continue;
}
while (!ps.empty() and !pointOnLineLeft(ps.back(), l)) {
ps.pop_back();
ls.pop_back();
}
while (!ps.empty() and !pointOnLineLeft(ps[0], l)) {
ps.pop_front();
ls.pop_front();
}
if (cross(l.b - l.a, ls.back().b - ls.back().a) == 0) {
if (dot(l.b - l.a, ls.back().b - ls.back().a) > 0) {
if (!pointOnLineLeft(ls.back().a, l)) {
assert(ls.size() == 1);
ls[0] = l;
}
continue;
}
return {};
}
ps.push_back(lineIntersection(ls.back(), l));
ls.push_back(l);
}
while (!ps.empty() and !pointOnLineLeft(ps.back(), ls[0])) {
ps.pop_back();
ls.pop_back();
}
if (ls.size() <= 2) {
return {};
}
ps.push_back(lineIntersection(ls[0], ls.back()));
return std::vector(ps.begin(), ps.end());
}
template<class T>
T PolygonArea(const std::vector<Point<T>> &p) {
T res = T(0);
int n = p.size();
for (int i = 0; i < n; i += 1) {
res += cross(p[i], p[(i + 1) % n]);
}
return std::abs(res);
}
template<class T>
std::vector<Point<T>> getHull(std::vector<Point<T>> p) {
std::vector<Point<T>>h, l;
std::sort(p.begin(), p.end(), [&](const auto & a, const auto & b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
});
p.erase(std::unique(p.begin(), p.end()), p.end());
if (p.size() <= 1) {
return p;
}
for (const auto & a : p) {
while ((int)h.size() > 1 and cross(a - h.back(), a - h[(int)h.size() - 2]) <= 0) {
h.pop_back();
}
while ((int)l.size() > 1 and cross(a - l.back(), a - l[(int)l.size() - 2]) >= 0) {
l.pop_back();
}
l.push_back(a);
h.push_back(a);
}
l.pop_back();
std::reverse(h.begin(), h.end());
h.pop_back();
l.insert(l.end(), h.begin(), h.end());
return l;
}
template<class T>
std::tuple<T, Point<T>, Point<T>> getLongest(const std::vector<Point<T>>& ret) {
std::vector<Point<T>> p = getHull(ret);
int n = p.size();
T res = T(0);
Point<T> a = Point<T>(), b = Point<T>();
int x = 0, y = 0;
for (int i = 0; i < n; i += 1) {
if (p[i].y < p[x].y)x = i;
if (p[i].y > p[y].y)y = i;
}
res = square(p[x] - p[y]);
a = p[x], b = p[y];
int i = x, j = y;
do {
if (cross(p[(i + 1) % n] - p[i], p[(j + 1) % n] - p[j]) < 0) {
i = (i + 1) % n;
} else {
j = (j + 1) % n;
}
if (square(p[i] - p[j]) > res) {
res = square(p[i] - p[j]);
a = p[i], b = p[j];
}
} while (i != x or j != y);
return {res, a, b};
}
template<class T>
std::tuple<T, Point<T>, Point<T>> getClostest(std::vector<Point<T>> p) {
std::sort(p.begin(), p.end(), [&](const auto & a, const auto & b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
});
T res = std::numeric_limits<T>::max();
Point<T> a = Point<T>(), b = Point<T>();
int n = p.size();
auto update = [&](const Point<T>& u, const Point<T>& v) {
if (res > square(u - v)) {
res = square(u - v);
a = u;
b = v;
}
};
auto s = std::multiset < Point<T>, decltype([](const Point<T>& u, const Point<T>& v) {
return u.y == v.y ? u.x < v.x : u.y < v.y;
}) > ();
std::vector<typename decltype(s)::const_iterator>its(n);
for (int i = 0, f = 0; i < n; i += 1) {
while (f < i and (p[i] - p[f]).x * (p[i] - p[f]).x >= res) {
s.erase(its[f++]);
}
auto u = s.upper_bound(p[i]); {
auto t = u;
while (true) {
if (t == s.begin()) {
break;
}
t = std::prev(t);
update(*t, p[i]);
if ((p[i] - *t).y * (p[i] - *t).y >= res) {
break;
}
}
}{
auto t = u;
while (true) {
if (t == s.end()) {
break;
}
if ((p[i] - *t).y * (p[i] - *t).y >= res) {
break;
}
update(*t, p[i]);
t = std::next(t);
}
}
its[i] = s.emplace_hint(u, p[i]);
}
return {res, a, b};
}
template<class T>
std::pair<T, std::vector<Point<T>>> rectCoverage(const std::vector<Point<T>>& p) {
T res = std::numeric_limits<T>::max();
std::vector<Point<T>>rect;
std::array<int, 4>pos {};
int n = p.size();
if (n < 3) {
return std::pair(res, rect);
}
for (int i = 0, r = 1, j = 1, q = 0; i < n; i += 1) {
while (cross(p[(i + 1) % n] - p[i], p[(r + 1) % n] - p[i]) >= cross(p[(i + 1) % n] - p[i], p[r] - p[i])) {
r = (r + 1) % n;
}
while (dot(p[(i + 1) % n] - p[i], p[(j + 1) % n] - p[i]) >= dot(p[(i + 1) % n] - p[i], p[j] - p[i])) {
j = (j + 1) % n;
}
if (i == 0) {
q = j;
}
while (dot(p[(i + 1) % n] - p[i], p[(q + 1) % n] - p[i]) <= dot(p[(i + 1) % n] - p[i], p[q] - p[i])) {
q = (q + 1) % n;
}
T d = square(p[i] - p[(i + 1) % n]);
T area = cross(p[(i + 1) % n] - p[i], p[r] - p[i]) * (dot(p[(i + 1) % n] - p[i], p[j] - p[i]) - dot(p[(i + 1) % n] - p[i], p[q] - p[i])) / d;
if (area < res) {
res = area;
pos[0] = r;
pos[1] = j;
pos[2] = q;
pos[3] = i;
}
}
const auto& [r, j, q, i] = pos;
Line<T> l1 = Line(p[i], p[(i + 1) % n]);
Point t = p[(i + 1) % n] - p[i];
Line<T> l2 = Line(p[r], p[r] + t);
t = rotate(t);
Line<T> l3 = Line(p[j], p[j] + t);
Line<T> l4 = Line(p[q], p[q] + t);
rect.push_back(lineIntersection(l1, l3));
rect.push_back(lineIntersection(l1, l4));
rect.push_back(lineIntersection(l2, l3));
rect.push_back(lineIntersection(l2, l4));
rect = getHull(rect);
return std::pair(res, rect);
}
template<class T>
Point<T> triangleHeart(const Point<T>& A, const Point<T>& B, const Point<T>& C) {
return (A * square(B - C) + B * square(C - A) + C * square(A - B)) / (square(B - C) + square(C - A) + square(A - B));
}
template<class T>
Point<T> circumcenter(const Point<T>& a, const Point<T>& b, const Point<T>& c) {
T D = 2 * (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
assert(D != 0);
Point<T> p;
p.x = ((square(a) * (b.y - c.y) + (square(b) * (c.y - a.y)) + (square(c) * (a.y - b.y)))) / D;
p.y = ((square(a) * (c.x - b.x) + (square(b) * (a.x - c.x)) + (square(c) * (b.x - a.x)))) / D;
return p;
}
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
template<class T>
std::pair<Point<T>, T> cirlCoverage(std::vector<Point<T>> p) {
for (int t = 0; t < 7; t += 1) {
std::shuffle(p.begin(), p.end(), rng);
}
int n = p.size();
Point<T> o = p[0];
T r = T(0);
for (int i = 1; i < n; i += 1) {
if (length(o - p[i]) > r) {
o = p[i];
r = T(0);
for (int j = 0; j < i; j += 1) {
if (length(o - p[j]) > r) {
o = (p[i] + p[j]) / T(2);
r = length(o - p[i]);
for (int k = 0; k < j; k += 1) {
if (length(o - p[k]) > r) {
o = circumcenter(p[i], p[j], p[k]);
r = length(o - p[i]);
}
}
}
}
}
}
return std::pair(o, r);
}
template<class F>
f64 integral(f64 l, f64 r, const F& f) {
static constexpr f64 eps = 1e-9;
auto simpson = [&](f64 l, f64 r) {
return (f(l) + 4 * f((l + r) / 2) + f(r)) * (r - l) / 6;
};
auto func = [&](auto && func, f64 l, f64 r, f64 eps, f64 st) {
f64 mid = (l + r) / 2;
f64 sl = simpson(l, mid), sr = simpson(mid, r);
if (std::abs(sl + sr - st) <= 15 * eps) {
return (sl + sr + (sl + sr - st) / 15);
}
return func(func, l, mid, eps / 2, sl) + func(func, mid, r, eps / 2, sr);
};
return func(func, l, r, eps, simpson(l, r));
}
using P = Point<i64>;
using L = Line<i64>;
const f64 pi = std::acos(-1.l);
auto main() ->int32_t {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::fixed << std::setprecision(13);
auto solve = [&]() {
int n, k;
std::cin >> n >> k;
std::vector<P>p(n);
for (auto & c : p) {
std::cin >> c;
}
if (n == k) {
std::cout << 2 * pi << '\n';
} else {
f64 res = 0;
std::sort(p.begin(), p.end(), [&](const auto & a, const auto & b) {
if (sgn(a) == sgn(b)) {
return cross(a, b) > 0;
}
return sgn(a) > sgn(b);
});
auto f = [&](const P & a) {
f64 r = angle(a);
if (r < 0) {
r += 2 * pi;
}
return r;
};
// for (const auto & c : p) {
// std::cout << f(c) << ' ';
// }
// std::cout << '\n';
for (int i = 0, j = k; i < n; i += 1, (j += 1) %= n) {
f64 t = 0;
if (j >= i) {
t = f(p[j]) - f(p[i]);
} else {
t = 2 * pi - f(p[i]) + f(p[j]);
}
chmax(res, t);
}
std::cout << res << '\n';
}
};
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3864kb
input:
5 1 1 0 1 8 2 1 0 1 1 0 1 -1 1 -1 0 -1 -1 0 -1 1 -1 4 2 -1 1 0 1 0 2 1 1 4 2 -1000000000 0 -998244353 1 998244353 1 1000000000 0 3 1 0 1 0 2 0 -1
output:
6.2831853071796 1.5707963267949 5.4977871437821 3.1415926545916 3.1415926535898
result:
ok 5 numbers
Test #2:
score: 0
Accepted
time: 30ms
memory: 3872kb
input:
10000 16 1 -10 -6 -5 -6 -4 9 -2 5 -2 10 1 -7 1 -5 1 6 3 1 4 -9 6 -10 6 -3 6 1 8 -5 8 -4 9 -4 17 4 -9 2 -8 -4 -8 -3 -8 -1 -6 -2 -6 -1 -6 8 -5 -8 -5 10 -4 8 -2 -8 4 -9 4 0 5 -3 8 -5 9 -2 10 10 10 6 -7 2 -4 6 -2 -7 -2 -1 -1 7 1 -9 1 8 3 -4 7 -4 9 -2 14 3 -9 10 -8 -10 -8 -8 -6 -7 -6 -5 -1 -7 -1 -2 0 -1 ...
output:
1.6929914974863 2.5748634360663 4.6527582672535 2.7726331073839 5.7427658069090 4.8576989910204 3.4198923125949 2.8127999620848 6.2831853071796 6.2831853071796 5.1172807666698 6.1467827027786 3.8420890235375 2.3424967168195 3.4633432079864 6.2831853071796 5.9614347527829 3.3247034708523 5.2627749280...
result:
ok 10000 numbers
Test #3:
score: 0
Accepted
time: 30ms
memory: 3940kb
input:
10000 19 7 -10 -6 -10 5 -3 0 -2 -5 -1 1 -1 6 0 3 0 7 1 9 3 -3 3 3 3 8 4 -1 5 8 6 -3 7 -5 7 4 8 10 9 -5 15 15 -9 -1 -8 6 -7 9 -6 -3 -4 -9 -1 -3 -1 8 1 -8 1 -7 3 -2 3 1 6 -9 7 -10 7 0 10 -9 10 3 -7 -1 -6 -2 -6 10 -5 2 -4 2 -3 -7 -2 -9 1 -3 3 4 7 7 15 4 -8 -8 -8 8 -7 0 -7 10 -6 -7 -5 6 -1 -3 -1 0 1 -2 ...
output:
3.9269908169872 6.2831853071796 3.3602615994637 2.6779450445890 3.7703889400052 1.7625844687816 3.8402524783113 5.4977871437821 2.0344439357957 1.8157749899218 4.3471875305965 6.1412882525754 5.1760365893855 5.4655402613469 5.7690391512670 4.3662530168153 5.9947557486612 4.8922424801772 4.1719694801...
result:
ok 10000 numbers
Test #4:
score: 0
Accepted
time: 29ms
memory: 3880kb
input:
10000 18 12 -10 -4 -10 7 -8 -10 -7 -4 -6 5 -6 7 -5 0 -2 -7 -1 2 -1 10 0 2 1 1 3 -2 5 3 5 5 6 -3 8 -3 9 -2 10 1 -10 -9 -7 -7 -5 2 -4 -7 -3 1 3 1 3 3 5 -4 9 2 9 6 11 2 -8 1 -8 6 -7 -2 -6 0 -5 0 -1 -9 2 -8 3 5 6 0 10 -2 10 6 20 9 -10 -6 -10 6 -9 -8 -7 5 -6 -4 -4 -8 -2 -10 -2 -3 -2 4 -1 1 2 -5 3 -2 5 -6...
output:
4.9097845402346 1.9756881130800 1.9868608325187 3.9269908169872 3.6977588837102 6.2831853071796 6.1412882525754 6.1938713141864 5.8053542521875 6.2528915472608 5.7288778109780 3.0900918426386 1.8925468811915 5.6341897481831 2.8966139904629 6.2831853071796 2.9147938055359 6.1476575931941 1.9513027039...
result:
ok 10000 numbers
Test #5:
score: 0
Accepted
time: 33ms
memory: 3872kb
input:
10000 19 7 -10 -1 -8 2 -7 -10 -6 6 -4 7 -3 -5 -3 1 -3 8 -2 4 -1 -7 0 -8 0 9 1 -10 2 1 2 3 3 5 6 -4 10 2 10 3 14 10 -8 2 -6 0 -5 -10 -5 10 -4 7 -3 -6 -2 -6 1 4 1 6 2 -1 3 -6 8 -4 9 -10 10 -1 12 8 -9 5 -7 2 -4 2 0 -2 0 5 1 6 3 2 4 9 5 5 7 -6 9 -9 9 2 19 12 -10 -10 -10 2 -9 -6 -8 2 -7 -5 -6 8 -4 1 -1 -...
output:
3.2393195609485 5.2757052418767 5.3003915839323 5.3871299226082 5.8883941874798 4.1173193566791 1.1383885512244 1.5152978215492 6.1476575931941 6.1588303126328 2.5748634360663 5.9401613667589 1.6085142792618 4.6099451268776 5.0711596506553 4.2345579253926 3.7905882125863 4.0376480381611 3.9160022483...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 33ms
memory: 3936kb
input:
10000 11 10 -10 -1 -9 4 -9 10 -7 -7 -5 4 -4 -1 -2 -10 0 -7 0 5 3 3 3 5 12 12 -9 6 -9 8 -3 -2 -2 2 0 -4 1 0 2 -3 3 5 5 -2 7 -1 10 3 10 9 14 12 -10 0 -9 -3 -9 1 -9 10 -8 -1 -8 7 -6 -1 -1 -6 -1 2 1 -1 3 -7 4 9 9 -3 10 1 10 4 -9 -3 -7 -1 -6 -10 -3 -2 -3 7 2 -2 2 3 5 2 6 9 9 6 10 2 -9 -9 -9 6 -8 3 -5 -9 ...
output:
6.1378752965439 6.2831853071796 6.1180366297650 3.2003484763055 2.6537562149302 6.2537820189756 3.6052402625906 3.5598169831690 1.5091461561556 5.9275494228788 6.2587998980069 2.6224465393433 4.3938333032966 5.4977871437821 4.2487413713839 5.4977871437821 4.6292477484962 3.5464844398749 6.0048856481...
result:
ok 10000 numbers
Test #7:
score: 0
Accepted
time: 34ms
memory: 3940kb
input:
10000 14 1 -100 13 -96 -31 -82 -92 -77 -98 -50 1 -14 -57 -14 -31 -11 64 -8 75 9 68 25 100 54 -36 59 13 93 31 19 19 -76 -39 -60 95 -51 18 -39 11 -21 -46 -6 -94 -5 83 -3 -34 -3 72 0 -55 3 79 14 17 23 -88 32 37 50 70 61 -5 62 -43 84 -100 97 -50 13 7 -99 -63 -68 -87 -24 62 -20 -18 -2 -66 7 -49 13 -21 15...
output:
1.2713093974613 6.2831853071796 5.2225147207365 6.0030657035689 3.9258721354647 5.5465289950921 3.2103149237117 3.0399300499237 4.2275317817944 3.0320196657369 2.1912152338182 3.0390080903677 4.3313271506355 6.2831853071796 5.1100022650512 2.9463140260615 5.1760365893855 5.6991835713711 2.0611798650...
result:
ok 10000 numbers
Test #8:
score: 0
Accepted
time: 34ms
memory: 3856kb
input:
100 1413 755 -30 -30 -30 -28 -30 -27 -30 -26 -30 -21 -30 -12 -30 -10 -30 -8 -30 -5 -30 -1 -30 2 -30 4 -30 7 -30 9 -30 17 -30 19 -30 20 -30 23 -30 24 -30 30 -29 -29 -29 -23 -29 -15 -29 0 -29 4 -29 5 -29 9 -29 10 -29 11 -29 12 -29 14 -29 16 -29 17 -29 22 -29 27 -29 28 -28 -28 -28 -25 -28 -23 -28 -22 -...
output:
3.5891126287470 2.9797552223514 0.2837941092083 2.0350277068911 4.8879811423349 1.0040671092714 4.7457099762629 5.3255963292592 4.3102749647329 5.6033836794138 1.5798050920853 4.3296454705391 5.5472220967941 1.4601391056210 1.5310445513990 2.8716749317081 2.6325789668605 3.1240505935324 0.6805212246...
result:
ok 100 numbers
Test #9:
score: 0
Accepted
time: 37ms
memory: 4084kb
input:
20 9045 8319 -1000 -986 -1000 -683 -1000 -430 -1000 -292 -1000 53 -1000 667 -999 -855 -999 -350 -999 -174 -999 -51 -999 -43 -999 235 -999 465 -999 530 -998 -997 -998 -311 -998 21 -998 44 -998 182 -997 -313 -997 -195 -997 -13 -997 412 -997 425 -996 -542 -996 -348 -996 -126 -996 -59 -996 -40 -996 84 -...
output:
5.9115110039040 3.7438685151377 2.5384828583153 2.1599673588579 4.2950377095723 4.7716744747962 4.6824078126019 5.0789843941746 1.6008018214107 3.3404025456367 3.3687925282503 2.1130160282301 4.8553994101327 4.3240010532705 0.1078535610706 0.1798211241778 5.3766547606521 4.4495660239030 4.3944016651...
result:
ok 20 numbers
Test #10:
score: 0
Accepted
time: 39ms
memory: 5648kb
input:
1 166347 18723 -1000 -979 -1000 -975 -1000 -928 -1000 -914 -1000 -898 -1000 -889 -1000 -876 -1000 -873 -1000 -858 -1000 -840 -1000 -838 -1000 -801 -1000 -783 -1000 -744 -1000 -738 -1000 -733 -1000 -713 -1000 -712 -1000 -695 -1000 -689 -1000 -680 -1000 -675 -1000 -671 -1000 -646 -1000 -643 -1000 -608...
output:
0.8514491789805
result:
ok found '0.8514492', expected '0.8514492', error '0.0000000'
Test #11:
score: 0
Accepted
time: 36ms
memory: 5948kb
input:
1 154903 84960 -1000 -979 -1000 -965 -1000 -956 -1000 -945 -1000 -920 -1000 -901 -1000 -878 -1000 -860 -1000 -858 -1000 -709 -1000 -693 -1000 -648 -1000 -619 -1000 -602 -1000 -579 -1000 -474 -1000 -473 -1000 -454 -1000 -443 -1000 -427 -1000 -407 -1000 -403 -1000 -384 -1000 -351 -1000 -279 -1000 -244...
output:
3.5389266853832
result:
ok found '3.5389267', expected '3.5389267', error '0.0000000'
Test #12:
score: 0
Accepted
time: 41ms
memory: 5824kb
input:
1 158037 96343 -1000 -1000 -1000 -905 -1000 -881 -1000 -833 -1000 -804 -1000 -803 -1000 -782 -1000 -775 -1000 -765 -1000 -759 -1000 -756 -1000 -748 -1000 -722 -1000 -674 -1000 -669 -1000 -630 -1000 -610 -1000 -573 -1000 -443 -1000 -411 -1000 -409 -1000 -403 -1000 -388 -1000 -366 -1000 -349 -1000 -33...
output:
3.9720287783259
result:
ok found '3.9720288', expected '3.9720288', error '0.0000000'
Test #13:
score: 0
Accepted
time: 43ms
memory: 3756kb
input:
10000 17 12 -853202371 684059854 -659446544 -924219854 -418025687 117998679 -399757126 -365708913 -331597239 -270896799 -204989763 869548983 -118492298 963842298 -77481232 672198731 45930201 -58234380 52605147 -900097542 78371985 940503934 235210685 595759114 391284089 234315077 416229789 -827244230...
output:
5.3985251100344 5.3739078748564 1.1735781728742 1.5443652595084 3.7782886494031 3.5704715868525 6.2829748588362 5.0959252028151 2.9875782465509 2.3055665058015 3.3907841641820 5.7854732381281 4.8109636122640 0.9567574180421 4.6294317309773 4.7995080628836 4.1702889055908 5.7394776963039 6.1210294479...
result:
ok 10000 numbers
Test #14:
score: 0
Accepted
time: 39ms
memory: 3848kb
input:
1000 133 108 -994106086 710243426 -991027749 -548437545 -983318226 -917527783 -943673956 -368162275 -935819096 616077188 -928022346 487569673 -924213856 -369318351 -914827619 426646545 -883935180 590882141 -870015071 -270471333 -834927107 -211343853 -829266515 354007200 -788041913 -60481736 -7822837...
output:
5.7428017921432 1.9153642398418 3.8043457981080 1.7919162705311 3.1695206706352 6.0786462146156 3.7860674595106 3.6659690726879 6.2265834529704 5.9021521926104 5.9443157092957 0.7151676870431 3.8315742529772 1.2228457184603 2.5984264669494 5.5473289205077 4.0791947427722 0.7042209930056 5.8578224268...
result:
ok 1000 numbers
Test #15:
score: 0
Accepted
time: 45ms
memory: 3864kb
input:
100 1367 924 -999416811 990355566 -997656126 346133696 -997071616 -657387469 -996176051 12622726 -995720693 334093112 -995478093 891631278 -994503890 341858449 -994297596 499383911 -993234202 533518057 -991636838 -4170504 -990563582 -407186200 -989454027 653116272 -989132124 -780605454 -988073521 -1...
output:
4.5051534906177 2.7125589326275 5.8396785809820 6.0229771114526 0.4616060431014 0.9869912332125 1.3219708488343 1.9258417458381 5.5086083533499 4.6463553312979 2.2876774102077 2.1848725877963 4.8094091918068 0.4770789902411 0.5563416050088 1.0936191641533 5.1827145536064 3.1131846618087 4.3802339550...
result:
ok 100 numbers
Test #16:
score: 0
Accepted
time: 43ms
memory: 4156kb
input:
10 13806 4955 -999669776 933068103 -999542354 721337508 -999499427 357140594 -999429088 -925180511 -999334813 -145726169 -999291694 -886327684 -999281647 811188099 -999145269 860687107 -998961821 -979442436 -998769313 446186367 -998591455 658309173 -998539751 -569480843 -998479467 279850955 -9984754...
output:
2.4170804680340 6.1611922290787 3.9600203768422 3.9943617929046 2.5515508361555 0.5227238367810 4.0978438278542 6.2103826631589 5.9817280292540 0.7772236858906
result:
ok 10 numbers
Test #17:
score: 0
Accepted
time: 37ms
memory: 4992kb
input:
1 112596 94970 -999980219 399324466 -999932413 952114487 -999894556 -951211102 -999891030 -996222974 -999864824 412806264 -999853190 -269700371 -999845814 -23906803 -999841507 -459154880 -999825178 716247149 -999761774 -154047106 -999729655 -171480333 -999709604 -666447277 -999704754 -22442485 -9996...
output:
5.4425938793439
result:
ok found '5.4425939', expected '5.4425939', error '0.0000000'
Test #18:
score: 0
Accepted
time: 53ms
memory: 5788kb
input:
1 161568 13252 -999991243 -113889211 -999976572 -361096764 -999970140 -505012445 -999960654 600963873 -999959339 -269932510 -999956568 734634576 -999941447 716485764 -999940305 64397798 -999939982 746532931 -999939921 995002380 -999932747 185078659 -999927136 585216518 -999914684 898656539 -99990452...
output:
0.6424745906865
result:
ok found '0.6424746', expected '0.6424746', error '0.0000000'
Test #19:
score: 0
Accepted
time: 62ms
memory: 6092kb
input:
1 186192 126483 -999998234 974001047 -999976292 -133179660 -999967957 112862981 -999957851 70030467 -999951528 743907713 -999931316 66002112 -999907988 888991267 -999905412 470798211 -999903986 -103943462 -999900422 255729004 -999898174 917068198 -999884392 -183592605 -999880179 -650076162 -99987469...
output:
4.4012456841190
result:
ok found '4.4012457', expected '4.4012457', error '0.0000000'
Test #20:
score: 0
Accepted
time: 37ms
memory: 3912kb
input:
1000 133 9 -10 -839744900 -10 -620593257 -10 -322048342 -10 578093727 -10 898998949 -9 -833794004 -9 -704882916 -9 -570204575 -9 -506146571 -9 -109555290 -9 309734100 -9 396668416 -8 -928874025 -8 376566668 -8 596463598 -8 600491164 -8 894775141 -7 -281322833 -7 49984651 -7 154512939 -7 205573228 -7...
output:
3.1415925828878 6.2831852482137 3.1415926144250 3.1415911740814 6.2831852702918 6.2831852953163 3.1415926492294 6.2831853036701 3.1415926401616 6.2831852506759 6.2831852816483 3.1415927591869 3.1415926453706 3.1415926237560 3.1415926152115 6.2831852733151 3.1415926493760 3.1415926537342 3.1415926532...
result:
ok 1000 numbers
Test #21:
score: 0
Accepted
time: 31ms
memory: 4416kb
input:
5 23120 8224 -10 -999575056 -10 -997485895 -10 -995458183 -10 -986953157 -10 -985268102 -10 -983223383 -10 -980910524 -10 -980404283 -10 -973605147 -10 -972441960 -10 -972440422 -10 -969122114 -10 -965754004 -10 -964812113 -10 -964558462 -10 -963159275 -10 -962972564 -10 -962085557 -10 -961552443 -1...
output:
3.1415926423514 3.1415926312424 3.1415926068008 3.1415926493953 6.2831852722069
result:
ok 5 numbers
Test #22:
score: 0
Accepted
time: 22ms
memory: 4684kb
input:
1 99995 60000 1 100001 1 100002 1 100003 1 100004 1 100005 1 100006 1 100007 1 100008 1 100009 1 100010 1 100011 1 100012 1 100013 1 100014 1 100015 1 100016 1 100017 1 100018 1 100019 1 100020 1 100021 1 100022 1 100023 1 100024 1 100025 1 100026 1 100027 1 100028 1 100029 1 100030 1 100031 1 10003...
output:
6.2831853069018
result:
ok found '6.2831853', expected '6.2831853', error '0.0000000'
Extra Test:
score: 0
Extra Test Passed