QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#298268#7906. Almost Convexucup-team133#WA 1ms4212kbC++2310.6kb2024-01-05 22:00:582024-01-05 22:00:58

Judging History

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

  • [2024-01-05 22:00:58]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4212kb
  • [2024-01-05 22:00:58]
  • 提交

answer

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

#include <type_traits>

namespace atcoder {

namespace internal {

#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value ||
                                  std::is_same<T, __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int128 =
    typename std::conditional<std::is_same<T, __uint128_t>::value ||
                                  std::is_same<T, unsigned __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using make_unsigned_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value,
                              __uint128_t,
                              unsigned __int128>;

template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
                                                  is_signed_int128<T>::value ||
                                                  is_unsigned_int128<T>::value,
                                              std::true_type,
                                              std::false_type>::type;

template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
                                                 std::is_signed<T>::value) ||
                                                    is_signed_int128<T>::value,
                                                std::true_type,
                                                std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<(is_integral<T>::value &&
                               std::is_unsigned<T>::value) ||
                                  is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<
    is_signed_int128<T>::value,
    make_unsigned_int128<T>,
    typename std::conditional<std::is_signed<T>::value,
                              std::make_unsigned<T>,
                              std::common_type<T>>::type>::type;

#else

template <class T> using is_integral = typename std::is_integral<T>;

template <class T>
using is_signed_int =
    typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<is_integral<T>::value &&
                                  std::is_unsigned<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
                                              std::make_unsigned<T>,
                                              std::common_type<T>>::type;

#endif

template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;

template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;

template <class T> using to_unsigned_t = typename to_unsigned<T>::type;

}  // namespace internal

}  // namespace atcoder

namespace atcoder {

// Reference: https://en.wikipedia.org/wiki/Fenwick_tree
template <class T> struct fenwick_tree {
    using U = internal::to_unsigned_t<T>;

  public:
    fenwick_tree() : _n(0) {}
    explicit fenwick_tree(int n) : _n(n), data(n) {}

    void add(int p, T x) {
        assert(0 <= p && p < _n);
        p++;
        while (p <= _n) {
            data[p - 1] += U(x);
            p += p & -p;
        }
    }

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        return sum(r) - sum(l);
    }

  private:
    int _n;
    std::vector<U> data;

    U sum(int r) {
        U s = 0;
        while (r > 0) {
            s += data[r - 1];
            r -= r & -r;
        }
        return s;
    }
};

}  // namespace atcoder

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> std::vector<int> convex_hull(const std::vector<Point<T>>& P, bool inclusive = false) {
    int n = P.size();
    if (n == 1) return {0};
    if (n == 2) return {0, 1};
    std::vector<int> ord(n);
    std::iota(begin(ord), end(ord), 0);
    std::sort(begin(ord), end(ord), [&](int l, int r) { return P[l] < P[r]; });
    std::vector<int> ch(n + 1, -1);
    int s = 0, t = 0;
    for (int _ = 0; _ < 2; _++, s = --t, std::reverse(begin(ord), end(ord))) {
        for (int& i : ord) {
            for (; t >= s + 2; t--) {
                auto det = (P[ch[t - 1]] - P[ch[t - 2]]).det(P[i] - P[ch[t - 2]]);
                if (inclusive ? det >= 0 : det > 0) break;
            }
            ch[t++] = i;
        }
    }
    return {begin(ch), begin(ch) + t - (t == 2 and ch[0] == ch[1])};
}

}  // namespace geometry

namespace geometry {

template <typename T> std::vector<int> sort_points_by_argument(const std::vector<Point<T>>& P) {
    auto type = [](const Point<T>& p) {
        if (p.x == 0 and p.y == 0) return 0;
        return (p.y < 0 or (p.y == 0 and p.x > 0)) ? -1 : 1;
    };
    int n = P.size();
    std::vector<int> res(n);
    std::iota(begin(res), end(res), 0);
    std::sort(begin(res), end(res), [&](int l, int r) {
        int L = type(P[l]), R = type(P[r]);
        return L != R ? L < R : P[l].x * P[r].y > P[l].y * P[r].x;
    });
    return res;
}

template <typename T> std::vector<int> sort_points_by_argument(const std::vector<std::pair<T, T>>& P) {
    std::vector<Point<T>> tmp;
    for (const auto& [x, y] : P) tmp.emplace_back(x, y);
    return sort_points_by_argument(tmp);
}

}  // namespace geometry

using namespace std;

typedef long long ll;
#define all(x) begin(x), end(x)
constexpr int INF = (1 << 30) - 1;
constexpr long long IINF = (1LL << 60) - 1;
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

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

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

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

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

template <class T> void mkuni(vector<T>& v) {
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
}

template <class T> int lwb(const vector<T>& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); }

using namespace geometry;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<Point<double>> ps(n);
    for (auto& p : ps) cin >> p;

    int ans = 1;
    auto conv_idx = convex_hull(ps);
    vector<bool> used(n, false);
    for (int& idx : conv_idx) used[idx] = true;
    vector<Point<double>> rest;
    for (int i = 0; i < n; i++) {
        if (not used[i]) {
            rest.emplace_back(ps[i]);
        }
    }
    int len = conv_idx.size();
    for (int i = 0; i < len; i++) {
        Point<double> L = ps[conv_idx[i]], R = ps[conv_idx[(i + 1) % len]];
        debug(L, R);
        double theta = (R - L).arg();
        vector<Point<double>> v;
        for (auto& p : rest) v.emplace_back((p - L).rotate(-theta));
        R = (R - L).rotate(-theta);
        L.x = L.y = 0;
        vector<int> cnt(n - len, 0);
        for (int _ = 0; _ < 2; _++) {
            auto ord = sort_points_by_argument(v);
            vector<Point<double>> nv(n - len);
            for (int j = 0; j < n - len; j++) nv[j] = v[ord[j]];
            swap(v, nv);
            vector<double> comp;
            for (auto& p : v) comp.emplace_back(p.x);
            mkuni(comp);
            int sz = comp.size();
            vector<int> X;
            for (auto& p : v) X.emplace_back(lwb(comp, p.x));
            atcoder::fenwick_tree<int> ft(sz);
            {
                for (int j = 0; j < n - len and comp[X[j]] > L.x; j++) {
                    cnt[ord[j]] += ft.sum(0, X[j] + 1);
                    ft.add(X[j], 1);
                }
                for (int j = 0; j < n - len and comp[X[j]] > L.x; j++) {
                    ft.add(X[j], -1);
                }
            }
            {
                for (int j = n - len - 1; j >= 0 and comp[X[j]] < L.x; j--) {
                    cnt[ord[j]] -= ft.sum(X[j], sz);
                    ft.add(X[j], 1);
                }
                for (int j = n - len - 1; j >= 0 and comp[X[j]] < L.x; j--) {
                    ft.add(X[j], -1);
                }
            }
            for (auto& p : ps) p.x = -p.x + R.x;
        }
        int sum = 0;
        for (int& val : cnt) sum += (val == 0);
        debug(L, R, theta, sum);
        ans += sum;
    }

    cout << ans << '\n';
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 4212kb

input:

7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 1ms
memory: 4116kb

input:

5
4 0
0 0
2 1
3 3
3 1

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 0ms
memory: 4172kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 4000kb

input:

6
0 0
3 0
3 2
0 2
1 1
2 1

output:

6

result:

wrong answer 1st numbers differ - expected: '7', found: '6'