QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#598082#9434. Italian Cuisineucup-team133#WA 0ms3704kbC++2310.2kb2024-09-28 20:26:422024-09-28 20:26:47

Judging History

你现在查看的是最新测评结果

  • [2024-09-28 20:26:47]
  • 评测
  • 测评结果：WA
  • 用时：0ms
  • 内存：3704kb
查看
  • [2024-09-28 20:26:42]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

template <class T> std::istream& operator>>(std::istream& is, std::vector<T>& v) {
    for (auto& e : v) {
        is >> e;
    }
    return is;
}

template <class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    for (std::string_view sep = ""; const auto& e : v) {
        os << std::exchange(sep, " ") << e;
    }
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) {
    return y < x and (x = std::forward<U>(y), true);
}

template <class T, class U = T> bool chmax(T& x, U&& y) {
    return x < y and (x = std::forward<U>(y), true);
}

template <class T> void mkuni(std::vector<T>& v) {
    std::ranges::sort(v);
    auto result = std::ranges::unique(v);
    v.erase(result.begin(), result.end());
}

template <class T> int lwb(const std::vector<T>& v, const T& x) {
    return std::distance(v.begin(), std::ranges::lower_bound(v, x));
}

#include <type_traits>

namespace geometry {

template <typename T> struct Point {
    static T EPS;

    static void set_eps(T eps) { EPS = eps; }

    T x, y;

    Point() {}

    Point(T x, T y) : x(x), y(y) {}

    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }

    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }

    Point operator*(T t) const { return Point(x * t, y * t); }

    Point operator/(T t) const { return Point(x / t, y / t); }

    bool operator==(const Point& p) const { return x == p.x and y == p.y; }

    bool operator!=(const Point& p) const { return not((*this) == p); }

    bool operator<(const Point& p) const { return x != p.x ? x < p.x : y < p.y; }

    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; }

    T norm() { return std::sqrt(x * x + y * y); }

    T norm2() { return x * x + y * y; }

    T arg() { return std::atan2(y, x); }

    T dot(const Point& p) { return x * p.x + y * p.y; }

    T det(const Point& p) { return x * p.y - y * p.x; }

    Point perp() { return Point(-y, x); }

    Point unit() { return *this / norm(); }

    Point normal() { return perp().unit(); }

    Point rotate(T rad) { return Point(std::cos(rad) * x - std::sin(rad) * y, std::sin(rad) * x + std::cos(rad) * y); }
};

template <> double Point<double>::EPS = 1e-9;
template <> long double Point<long double>::EPS = 1e-12;
template <> int Point<int>::EPS = 0;
template <> long long Point<long long>::EPS = 0;

template <typename T> int sgn(T x) { return x < -Point<T>::EPS ? -1 : x > Point<T>::EPS ? 1 : 0; }

}  // namespace geometry

namespace geometry {

template <typename T> struct Circle {
    Point<T> c;
    T r;

    Circle() {}

    Circle(Point<T> c, T r) : c(c), r(r) {}

    friend std::istream& operator>>(std::istream& is, Circle& c) { return is >> c.c >> c.r; }

    friend std::ostream& operator<<(std::ostream& os, const Circle& c) { return os << c.c << ' ' << c.r; }
};

}  // namespace geometry

namespace geometry {

enum Position { COUNTER_CLOCKWISE = +1, CLOCKWISE = -1, ONLINE_BACK = +2, ONLINE_FRONT = -2, ON_SEGMENT = 0 };

template <typename T> Position ccw(const Point<T>& a, Point<T> b, Point<T> c) {
    b = b - a;
    c = c - a;
    if (sgn(b.det(c)) == 1) return COUNTER_CLOCKWISE;
    if (sgn(b.det(c)) == -1) return CLOCKWISE;
    if (sgn(b.dot(c)) == -1) return ONLINE_BACK;
    if (b.norm2() < c.norm2()) return ONLINE_FRONT;
    return ON_SEGMENT;
}

}  // namespace geometry

namespace geometry {

template <typename T> struct Polygon : std::vector<Point<T>> {
    using std::vector<Point<T>>::vector;

    Polygon(int n) : std::vector<Point<T>>(n) {}

    T area2() {
        T sum = 0;
        int n = this->size();
        for (int i = 0; i < n; i++) sum += (*this)[i].det((*this)[i + 1 == n ? 0 : i + 1]);
        return sum < 0 ? -sum : sum;
    }

    T area() { return area2() / 2; }

    bool is_convex() {
        int n = this->size();
        for (int j = 0; j < n; j++) {
            int i = (j == 0 ? n - 1 : j - 1), k = (j == n - 1 ? 0 : j + 1);
            if (ccw((*this)[i], (*this)[j], (*this)[k]) == CLOCKWISE) return false;
        }
        return true;
    }
};

}  // namespace geometry

namespace geometry {

template <typename T> struct Line {
    Point<T> a, b;

    Line() {}

    Line(const Point<T>& a, const Point<T>& b) : a(a), b(b) {}

    // A * x + B * y + C = 0
    Line(T A, T B, T C) {}

    friend std::istream& operator>>(std::istream& is, Line& l) { return is >> l.a >> l.b; }

    friend std::ostream& operator<<(std::ostream& os, const Line& l) { return os << l.a << " to " << l.b; }
};

template <typename T> struct Segment : Line<T> {
    Segment() {}

    Segment(const Point<T>& a, const Point<T>& b) : Line<T>(a, b) {}
};

}  // namespace geometry

namespace geometry {

template <typename T> Point<T> projection(const Line<T>& l, const Point<T>& p) {
    Point<T> a = p - l.a, b = l.b - l.a;
    return l.a + b * a.dot(b) / b.norm2();
}

}  // namespace geometry

namespace geometry {

template <typename T> bool is_parallel(const Line<T>& l, const Line<T>& m) {
    return sgn((l.b - l.a).det(m.b - m.a)) == 0;
}

template <typename T> bool is_orthogonal(const Line<T>& l, const Line<T>& m) {
    return sgn((l.b - l.a).dot(m.b - m.a)) == 0;
}

template <typename T> bool has_crosspoint(const Segment<T>& s, const Segment<T>& t) {
    return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 and ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}

template <typename T> int count_common_tangent(const Circle<T>& c, const Circle<T>& d) {
    T dist = (c.c - d.c).norm();
    int tmp = sgn(dist - (c.r + d.r));
    if (tmp > 0) return 4;
    if (tmp == 0) return 3;
    tmp = sgn(dist - (sgn(c.r - d.r) > 0 ? c.r - d.r : d.r - c.r));
    if (tmp > 0) return 2;
    if (tmp == 0) return 1;
    return 0;
}

template <typename T> Point<T> crosspoint(const Line<T>& l, const Line<T>& m) {
    assert(not is_parallel(l, m));
    Point<T> u = l.b - l.a, v = m.b - m.a;
    return l.a + u * v.det(m.a - l.a) / v.det(u);
}

template <typename T> Point<T> crosspoint(const Segment<T>& s, const Segment<T>& t) {
    assert(has_crosspoint(s, t));
    if (not is_parallel(s, t)) return crosspoint(Line(s.a, s.b), Line(t.a, t.b));
    std::vector<Point<T>> v = {s.a, s.b, t.a, t.b};
    for (int i = 0; i <= 2; i++) {
        for (int j = 2; j >= i; j--) {
            if (v[j + 1] < v[j]) {
                std::swap(v[j], v[j + 1]);
            }
        }
    }
    return v[1];
}

template <typename T> std::vector<Point<T>> crosspoint(const Circle<T>& c, const Line<T>& l) {
    Point<T> h = projection(l, c.c);
    T x = c.r * c.r - (c.c - h).norm2();
    if (sgn(x) < 0) return {};
    if (sgn(x) == 0) return {h};
    Point<T> v = (l.b - l.a).unit() * std::sqrt(x);
    return {h - v, h + v};
}

template <typename T> std::vector<Point<T>> crosspoint(const Circle<T>& c, const Segment<T>& s) {}

template <typename T> std::vector<Point<T>> crosspoint(const Circle<T>& c1, const Circle<T>& c2) {
    T r1 = c1.r, r2 = c2.r;
    if (r1 < r2) return crosspoint(c2, c1);
    T d = (c2.c - c1.c).norm();
    if (sgn(d - (r1 + r2)) > 0 or sgn(d - (r1 - r2)) < 0) return {};
    Point<T> v = c2.c - c1.c;
    if (sgn(d - (r1 + r2)) == 0 or sgn(d - (r1 - r2)) == 0) return {c1.c + v.unit() * r1};
    T p = ((r1 * r1 - r2 * r2) / d + d) / 2, q = std::sqrt(r1 * r1 - p * p);
    Point<T> h = c1.c + v.unit() * p;
    Point<T> i = v.normal();
    return {h + i * q, h - i * q};
}

}  // namespace geometry

namespace geometry {

template <typename T> T distance(const Point<T>& p, const Point<T>& q) { return (p - q).norm(); }

template <typename T> T distance(const Line<T>& l, const Point<T>& p) { return distance(p, projection(l, p)); }

template <typename T> T distance(const Segment<T>& s, const Point<T>& p) {
    Point<T> h = projection(s, p);
    return ccw(s.a, s.b, h) == ON_SEGMENT ? distance(p, h) : std::min(distance(p, s.a), distance(p, s.b));
}

template <typename T> T distance(const Segment<T>& s, const Segment<T>& t) {
    return has_crosspoint(s, t) ? 0
                                : std::min({distance(s, t.a), distance(s, t.b), distance(t, s.a), distance(t, s.b)});
}

}  // namespace geometry

using ll = long long;

using namespace std;

using namespace geometry;

void solve() {
    int n;
    cin >> n;
    Circle<long double> c;
    cin >> c;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];

    Polygon<long double> p;
    Polygon<ll> q;
    for (int i = 0; i < n; i++) {
        p.emplace_back(x[i], y[i]);
        q.emplace_back(x[i], y[i]);
    }
    vector<ll> area(2 * n);
    for (int i = 0; i < 2 * n; i++) area[i] = q[i % n].det(q[(i + 1) % n]);
    vector<ll> sum(2 * n + 1);
    sum[0] = 0;
    for (int i = 0; i < 2 * n; i++) sum[i + 1] = sum[i] + area[i];

    auto calc = [&](int l, int r) -> ll {
        int R = (r < l ? r + n : r);
        if (R - l < 2) return 0;
        ll res = sum[R] - sum[l];
        res += q[r].det(q[l]);
        return abs(res);
    };

    ll ans = 0;
    for (int i = 0; i < n; i++) {
        auto m = (p[i] + c.c) / 2;
        auto tan = crosspoint(c, Circle<long double>(m, distance(p[i], m)));
        if (int(tan.size()) != 2) continue;
        {
            int lb = 1, ub = n;
            while (ub - lb > 1) {
                int mid = (lb + ub) >> 1;
                (ccw(p[i], tan[0], p[(i + mid) % n]) != COUNTER_CLOCKWISE and
                         ccw(p[i], tan[1], p[(i + mid) % n]) != COUNTER_CLOCKWISE
                     ? lb
                     : ub) = mid;
            }
            chmax(ans, calc(i, (i + lb) % n));
        }
        {
            int lb = 0, ub = n - 1;
            while (ub - lb > 1) {
                int mid = (lb + ub) >> 1;
                (ccw(p[i], tan[0], p[(i + mid) % n]) != CLOCKWISE and ccw(p[i], tan[1], p[(i + mid) % n]) != CLOCKWISE
                     ? ub
                     : lb) = mid;
            }
            chmax(ans, calc((i + ub) % n, i));
        }
    }

    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int T;
    cin >> T;
    for (; T--;) solve();
    return 0;
}
源文件, 语言: C++23

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3652kb

input:

3
5
1 1 1
0 0
1 0
5 0
3 3
0 5
6
2 4 1
2 0
4 0
6 3
4 6
2 6
0 3
4
3 3 1
3 0
6 3
3 6
0 3

output:

5
24
0

result:

ok 3 number(s): "5 24 0"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3704kb

input:

1
6
0 0 499999993
197878055 -535013568
696616963 -535013568
696616963 40162440
696616963 499999993
-499999993 499999993
-499999993 -535013568

output:

286862654137719264

result:

wrong answer 1st numbers differ - expected: '0', found: '286862654137719264'
English 繁體中文 简体中文

伺服器時間: 2025-01-22 12:32:52 | 開源專案