QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#805379 | #9869. Horizon Scanning | jayket | WA | 25ms | 4240kb | C++23 | 20.7kb | 2024-12-08 16:20:36 | 2024-12-08 16:20:37 |
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(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);
r += 2 * pi;
return r;
};
for (int i = 0, j = k; i < n; i += 1, (j += 1) %= n) {
f64 t = f(p[j]) - f(p[i]);
if (t < 0) {
t += 2 * pi;
}
chmax(res, t);
}
std::cout << res << '\n';
}
};
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4168kb
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: -100
Wrong Answer
time: 25ms
memory: 4240kb
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:
wrong answer 42nd numbers differ - expected: '6.2831853', found: '6.2599337', error = '0.0037006'