QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#298268 | #7906. Almost Convex | ucup-team133# | WA | 1ms | 4212kb | C++23 | 10.6kb | 2024-01-05 22:00:58 | 2024-01-05 22:00:58 |
Judging History
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'