結果
| 問題 |
No.3074 Divide Points Fairly
|
| ユーザー |
 kk2a
|
| 提出日時 | 2025-03-31 06:36:43 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 41 ms / 2,000 ms |
| コード長 | 36,889 bytes |
| コンパイル時間 | 3,715 ms |
| コンパイル使用メモリ | 228,632 KB |
| 実行使用メモリ | 7,324 KB |
| 最終ジャッジ日時 | 2025-03-31 06:36:51 |
| 合計ジャッジ時間 | 7,157 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 42 |
ソースコード
#include <utility>
#include <type_traits>
#include <algorithm>
#include <istream>
#include <map>
#include <iterator>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <ostream>
#include <iostream>
#include <numeric>
#include <queue>
#include <cassert>
#include <optional>
#include <vector>
#include <string>
#include <set>
#include <deque>
#include <unordered_set>
#include <stack>
#include <unordered_map>
#include <functional>
#include <fstream>
#include <array>
#include <bitset>
#ifndef KK2_TEMPLATE_PROCON_HPP
#define KK2_TEMPLATE_PROCON_HPP 1
#ifndef KK2_TEMPLATE_CONSTANT_HPP
#define KK2_TEMPLATE_CONSTANT_HPP 1
#ifndef KK2_TEMPLATE_TYPE_ALIAS_HPP
#define KK2_TEMPLATE_TYPE_ALIAS_HPP 1
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using pi = std::pair<int, int>;
using pl = std::pair<i64, i64>;
using pil = std::pair<int, i64>;
using pli = std::pair<i64, int>;
template <class T> using vc = std::vector<T>;
template <class T> using vvc = std::vector<vc<T>>;
template <class T> using vvvc = std::vector<vvc<T>>;
template <class T> using vvvvc = std::vector<vvvc<T>>;
template <class T> using pq = std::priority_queue<T>;
template <class T> using pqi = std::priority_queue<T, std::vector<T>, std::greater<T>>;
#endif // KK2_TEMPLATE_TYPE_ALIAS_HPP
template <class T> constexpr T infty = 0;
template <> constexpr int infty<int> = (1 << 30) - 123;
template <> constexpr i64 infty<i64> = (1ll << 62) - (1ll << 31);
template <> constexpr i128 infty<i128> = (i128(1) << 126) - (i128(1) << 63);
template <> constexpr u32 infty<u32> = infty<int>;
template <> constexpr u64 infty<u64> = infty<i64>;
template <> constexpr u128 infty<u128> = infty<i128>;
template <> constexpr double infty<double> = infty<i64>;
template <> constexpr long double infty<long double> = infty<i64>;
constexpr int mod = 998244353;
constexpr int modu = 1e9 + 7;
constexpr long double PI = 3.14159265358979323846;
#endif // KK2_TEMPLATE_CONSTANT_HPP
#ifndef KK2_TEMPLATE_FUNCTION_UTIL_HPP
#define KK2_TEMPLATE_FUNCTION_UTIL_HPP 1
namespace kk2 {
template <class T, class... Sizes> auto make_vector(int first, Sizes... sizes) {
if constexpr (sizeof...(sizes) == 0) {
return std::vector<T>(first);
} else {
return std::vector<decltype(make_vector<T>(sizes...))>(first, make_vector<T>(sizes...));
}
}
template <class T, class U> void fill_all(std::vector<T> &v, const U &x) {
std::fill(std::begin(v), std::end(v), T(x));
}
template <class T, class U> void fill_all(std::vector<std::vector<T>> &v, const U &x) {
for (auto &u : v) fill_all(u, x);
}
template <class C> int mysize(const C &c) {
return c.size();
}
// T: comutative monoid
template <class T, class U> U all_sum(const std::vector<T> &v, U init, U = U()) {
U res = init;
for (const auto &x : v) res += x;
return res;
}
template <class T, class U> U all_sum(const std::vector<std::vector<T>> &v, U init, U unit = U()) {
U res = init;
for (const auto &u : v) res += all_sum(u, unit, unit);
return res;
}
// T: commutative monoid, F: (U, T) -> U
template <class T, class U, class F> U all_prod(const std::vector<T> &v, U init, const F &f, U = U()) {
U res = init;
for (const auto &x : v) res = f(res, x);
return res;
}
template <class T, class U, class F>
U all_prod(const std::vector<std::vector<T>> &v, U init, const F &f, U unit) {
U res = init;
for (const auto &u : v) res = f(res, all_prod(u, unit, f, unit));
return res;
}
template <class T> T all_min(const std::vector<T> &v) {
if (v.empty()) return T();
T res = v[0];
for (const auto &x : v) res = res > x ? x : res;
return res;
}
template <class T>
T all_min(const std::vector<std::vector<T>> &v) {
T res{};
bool first = true;
for (const auto &u : v) {
if (u.empty()) continue;
if (first) {
res = all_min(u);
first = false;
} else {
T tmp = all_min(u);
res = res > tmp ? tmp : res;
}
}
return res;
}
template <class T> T all_max(const std::vector<T> &v) {
if (v.empty()) return T();
T res = v[0];
for (const auto &x : v) res = res < x ? x : res;
return res;
}
template <class T>
T all_max(const std::vector<std::vector<T>> &v) {
T res{};
bool first = true;
for (const auto &u : v) {
if (u.empty()) continue;
if (first) {
res = all_max(u);
first = false;
} else {
T tmp = all_max(u);
res = res < tmp ? tmp : res;
}
}
return res;
}
} // namespace kk2
#endif // KK2_TEMPLATE_FUNCTION_UTIL_HPP
#ifndef KK2_TEMPLATE_IO_UTIL_HPP
#define KK2_TEMPLATE_IO_UTIL_HPP 1
#ifndef KK2_TYPE_TRAITS_TYPE_TRAITS_HPP
#define KK2_TYPE_TRAITS_TYPE_TRAITS_HPP 1
namespace kk2 {
#ifndef _MSC_VER
template <typename T>
using is_signed_int128 = typename std::conditional<std::is_same<T, __int128_t>::value
or std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value
or std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_integral =
typename std::conditional<std::is_integral<T>::value or is_signed_int128<T>::value
or is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_signed = typename std::conditional<std::is_signed<T>::value or is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_unsigned =
typename std::conditional<std::is_unsigned<T>::value or is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value, __uint128_t, unsigned __int128>;
template <typename 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 <typename T> using is_integral = std::enable_if_t<std::is_integral<T>::value>;
template <typename T> using is_signed = std::enable_if_t<std::is_signed<T>::value>;
template <typename T> using is_unsigned = std::enable_if_t<std::is_unsigned<T>::value>;
template <typename T> using to_unsigned = std::make_unsigned<T>;
#endif // _MSC_VER
template <typename T> using is_integral_t = std::enable_if_t<is_integral<T>::value>;
template <typename T> using is_signed_t = std::enable_if_t<is_signed<T>::value>;
template <typename T> using is_unsigned_t = std::enable_if_t<is_unsigned<T>::value>;
template <typename T>
using is_function_pointer =
typename std::conditional<std::is_pointer_v<T> && std::is_function_v<std::remove_pointer_t<T>>,
std::true_type,
std::false_type>::type;
template <typename T, std::enable_if_t<is_function_pointer<T>::value> * = nullptr>
struct is_two_args_function_pointer : std::false_type {};
template <typename R, typename T1, typename T2>
struct is_two_args_function_pointer<R (*)(T1, T2)> : std::true_type {};
template <typename T>
using is_two_args_function_pointer_t = std::enable_if_t<is_two_args_function_pointer<T>::value>;
namespace type_traits {
struct istream_tag {};
struct ostream_tag {};
} // namespace type_traits
template <typename T>
using is_standard_istream = typename std::conditional<std::is_same<T, std::istream>::value
|| std::is_same<T, std::ifstream>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_standard_ostream = typename std::conditional<std::is_same<T, std::ostream>::value
|| std::is_same<T, std::ofstream>::value,
std::true_type,
std::false_type>::type;
template <typename T> using is_user_defined_istream = std::is_base_of<type_traits::istream_tag, T>;
template <typename T> using is_user_defined_ostream = std::is_base_of<type_traits::ostream_tag, T>;
template <typename T>
using is_istream =
typename std::conditional<is_standard_istream<T>::value || is_user_defined_istream<T>::value,
std::true_type,
std::false_type>::type;
template <typename T>
using is_ostream =
typename std::conditional<is_standard_ostream<T>::value || is_user_defined_ostream<T>::value,
std::true_type,
std::false_type>::type;
template <typename T> using is_istream_t = std::enable_if_t<is_istream<T>::value>;
template <typename T> using is_ostream_t = std::enable_if_t<is_ostream<T>::value>;
} // namespace kk2
#endif // KK2_TYPE_TRAITS_TYPE_TRAITS_HPP
// なんかoj verifyはプロトタイプ宣言が落ちる
namespace impl {
struct read {
template <class IStream, class T>
inline static void all_read(IStream &is, T &x) {
is >> x;
}
template <class IStream, class T, class U>
inline static void all_read(IStream &is, std::pair<T, U> &p) {
all_read(is, p.first);
all_read(is, p.second);
}
template <class IStream, class T>
inline static void all_read(IStream &is, std::vector<T> &v) {
for (T &x : v) all_read(is, x);
}
template <class IStream, class T, size_t F>
inline static void all_read(IStream &is, std::array<T, F> &a) {
for (T &x : a) all_read(is, x);
}
};
struct write {
template <class OStream, class T>
inline static void all_write(OStream &os, const T &x) {
os << x;
}
template <class OStream, class T, class U>
inline static void all_write(OStream &os, const std::pair<T, U> &p) {
all_write(os, p.first);
all_write(os, ' ');
all_write(os, p.second);
}
template <class OStream, class T>
inline static void all_write(OStream &os, const std::vector<T> &v) {
for (int i = 0; i < (int)v.size(); ++i) {
if (i) all_write(os, ' ');
all_write(os, v[i]);
}
}
template <class OStream, class T, size_t F>
inline static void all_write(OStream &os, const std::array<T, F> &a) {
for (int i = 0; i < (int)F; ++i) {
if (i) all_write(os, ' ');
all_write(os, a[i]);
}
}
};
} // namespace impl
template <class IStream, class T, class U, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::pair<T, U> &p) {
impl::read::all_read(is, p);
return is;
}
template <class IStream, class T, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::vector<T> &v) {
impl::read::all_read(is, v);
return is;
}
template <class IStream, class T, size_t F, kk2::is_istream_t<IStream> * = nullptr>
IStream &operator>>(IStream &is, std::array<T, F> &a) {
impl::read::all_read(is, a);
return is;
}
template <class OStream, class T, class U, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::pair<T, U> &p) {
impl::write::all_write(os, p);
return os;
}
template <class OStream, class T, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::vector<T> &v) {
impl::write::all_write(os, v);
return os;
}
template <class OStream, class T, size_t F, kk2::is_ostream_t<OStream> * = nullptr>
OStream &operator<<(OStream &os, const std::array<T, F> &a) {
impl::write::all_write(os, a);
return os;
}
#endif // KK2_TEMPLATE_IO_UTIL_HPP
#ifndef KK2_TEMPLATE_MACROS_HPP
#define KK2_TEMPLATE_MACROS_HPP 1
#define rep1(a) for (long long _ = 0; _ < (long long)(a); ++_)
#define rep2(i, a) for (long long i = 0; i < (long long)(a); ++i)
#define rep3(i, a, b) for (long long i = (a); i < (long long)(b); ++i)
#define repi2(i, a) for (long long i = (a) - 1; i >= 0; --i)
#define repi3(i, a, b) for (long long i = (a) - 1; i >= (long long)(b); --i)
#define overload3(a, b, c, d, ...) d
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define repi(...) overload3(__VA_ARGS__, repi3, repi2, rep1)(__VA_ARGS__)
#define fi first
#define se second
#define all(p) p.begin(), p.end()
#endif // KK2_TEMPLATE_MACROS_HPP
struct FastIOSetUp {
FastIOSetUp() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
}
} fast_io_set_up;
auto &kin = std::cin;
auto &kout = std::cout;
auto (*kendl)(std::ostream &) = std::endl<char, std::char_traits<char>>;
void Yes(bool b = 1) {
kout << (b ? "Yes\n" : "No\n");
}
void No(bool b = 1) {
kout << (b ? "No\n" : "Yes\n");
}
void YES(bool b = 1) {
kout << (b ? "YES\n" : "NO\n");
}
void NO(bool b = 1) {
kout << (b ? "NO\n" : "YES\n");
}
void yes(bool b = 1) {
kout << (b ? "yes\n" : "no\n");
}
void no(bool b = 1) {
kout << (b ? "no\n" : "yes\n");
}
template <class T, class S> inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template <class T, class S> inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
std::istream &operator>>(std::istream &is, u128 &x) {
std::string s;
is >> s;
x = 0;
for (char c : s) {
assert('0' <= c && c <= '9');
x = x * 10 + c - '0';
}
return is;
}
std::istream &operator>>(std::istream &is, i128 &x) {
std::string s;
is >> s;
bool neg = s[0] == '-';
x = 0;
for (int i = neg; i < (int)s.size(); i++) {
assert('0' <= s[i] && s[i] <= '9');
x = x * 10 + s[i] - '0';
}
if (neg) x = -x;
return is;
}
std::ostream &operator<<(std::ostream &os, u128 x) {
if (x == 0) return os << '0';
std::string s;
while (x) {
s.push_back('0' + x % 10);
x /= 10;
}
std::reverse(s.begin(), s.end());
return os << s;
}
std::ostream &operator<<(std::ostream &os, i128 x) {
if (x == 0) return os << '0';
if (x < 0) {
os << '-';
x = -x;
}
std::string s;
while (x) {
s.push_back('0' + x % 10);
x /= 10;
}
std::reverse(s.begin(), s.end());
return os << s;
}
#endif // KK2_TEMPLATE_PROCON_HPP
#ifndef KK2_TEMPLATE_DEBUG_HPP
#define KK2_TEMPLATE_DEBUG_HPP 1
#ifndef KK2_TYPE_TRAITS_MEMBER_HPP
#define KK2_TYPE_TRAITS_MEMBER_HPP 1
namespace kk2 {
#define HAS_MEMBER_FUNC(member) \
template <typename T, typename... Ts> struct has_member_func_##member##_impl { \
template <typename U> \
static std::true_type check(decltype(std::declval<U>().member(std::declval<Ts>()...)) *); \
template <typename U> static std::false_type check(...); \
using type = decltype(check<T>(nullptr)); \
}; \
template <typename T, typename... Ts> \
struct has_member_func_##member : has_member_func_##member##_impl<T, Ts...>::type {}; \
template <typename T, typename... Ts> \
using has_member_func_##member##_t = \
std::enable_if_t<has_member_func_##member<T, Ts...>::value>; \
template <typename T, typename... Ts> \
using not_has_member_func_##member##_t = \
std::enable_if_t<!has_member_func_##member<T, Ts...>::value>;
#define HAS_MEMBER_VAR(member) \
template <typename T> struct has_member_var_##member##_impl { \
template <typename U> static std::true_type check(decltype(std::declval<U>().member) *); \
template <typename U> static std::false_type check(...); \
using type = decltype(check<T>(nullptr)); \
}; \
template <typename T> \
struct has_member_var_##member : has_member_var_##member##_impl<T>::type {}; \
template <typename T> \
using has_member_var_##member##_t = std::enable_if_t<has_member_var_##member<T>::value>; \
template <typename T> \
using not_has_member_var_##member##_t = std::enable_if_t<!has_member_var_##member<T>::value>;
HAS_MEMBER_FUNC(debug_output)
HAS_MEMBER_FUNC(val)
#undef HAS_MEMBER_FUNC
#undef HAS_MEMBER_VAR
} // namespace kk2
#endif // KK2_TYPE_TRAITS_MEMBER_HPP
namespace kk2 {
namespace debug {
#ifdef KK2
template <class OStream, is_ostream_t<OStream> *> void output(OStream &os);
template <class OStream, class T, is_ostream_t<OStream> *> void output(OStream &os, const T &t);
template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::vector<T> &v);
template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::vector<std::vector<T>> &d);
template <class OStream, class T, size_t F, is_ostream_t<OStream> *>
void output(OStream &os, const std::array<T, F> &a);
template <class OStream, class T, class U, is_ostream_t<OStream> *>
void output(OStream &os, const std::pair<T, U> &p);
template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::queue<T> &q);
template <class OStream, class T, class Container, class Compare, is_ostream_t<OStream> *>
void output(OStream &os, const std::priority_queue<T, Container, Compare> &q);
template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::deque<T> &d);
template <class OStream, class T, is_ostream_t<OStream> *>
void output(OStream &os, const std::stack<T> &s);
template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> *>
void output(OStream &os, const std::set<Key, Compare, Allocator> &s);
template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> *>
void output(OStream &os, const std::multiset<Key, Compare, Allocator> &s);
template <class OStream,
class Key,
class Hash,
class KeyEqual,
class Allocator,
is_ostream_t<OStream> *>
void output(OStream &os, const std::unordered_set<Key, Hash, KeyEqual, Allocator> &s);
template <class OStream,
class Key,
class Hash,
class KeyEqual,
class Allocator,
is_ostream_t<OStream> *>
void output(OStream &os, const std::unordered_multiset<Key, Hash, KeyEqual, Allocator> &s);
template <class OStream,
class Key,
class T,
class Compare,
class Allocator,
is_ostream_t<OStream> *>
void output(OStream &os, const std::map<Key, T, Compare, Allocator> &m);
template <class OStream,
class Key,
class T,
class Hash,
class KeyEqual,
class Allocator,
is_ostream_t<OStream> *>
void output(OStream &os, const std::unordered_map<Key, T, Hash, KeyEqual, Allocator> &m);
template <class OStream, is_ostream_t<OStream> * = nullptr> void output(OStream &) {
}
template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const T &t) {
if constexpr (has_member_func_debug_output<T, OStream &>::value) {
t.debug_output(os);
} else {
os << t;
}
}
template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::vector<T> &v) {
os << "[";
for (int i = 0; i < (int)v.size(); i++) {
output(os, v[i]);
if (i + 1 != (int)v.size()) os << ", ";
}
os << "]";
}
template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::vector<std::vector<T>> &d) {
os << "[\n";
for (int i = 0; i < (int)d.size(); i++) {
output(os, d[i]);
output(os, "\n");
}
os << "]";
}
template <class OStream, class T, size_t F, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::array<T, F> &a) {
os << "[";
for (int i = 0; i < (int)F; i++) {
output(os, a[i]);
if (i + 1 != (int)F) os << ", ";
}
os << "]";
}
template <class OStream, class T, class U, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::pair<T, U> &p) {
os << "(";
output(os, p.first);
os << ", ";
output(os, p.second);
os << ")";
}
template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::queue<T> &q) {
os << "[";
std::queue<T> tmp = q;
while (!tmp.empty()) {
output(os, tmp.front());
tmp.pop();
if (!tmp.empty()) os << ", ";
}
os << "]";
}
template <class OStream, class T, class Container, class Compare, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::priority_queue<T, Container, Compare> &q) {
os << "[";
std::priority_queue<T, Container, Compare> tmp = q;
while (!tmp.empty()) {
output(os, tmp.top());
tmp.pop();
if (!tmp.empty()) os << ", ";
}
os << "]";
}
template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::deque<T> &d) {
os << "[";
std::deque<T> tmp = d;
while (!tmp.empty()) {
output(os, tmp.front());
tmp.pop_front();
if (!tmp.empty()) os << ", ";
}
os << "]";
}
template <class OStream, class T, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::stack<T> &s) {
os << "[";
std::stack<T> tmp = s;
std::vector<T> v;
while (!tmp.empty()) {
v.push_back(tmp.top());
tmp.pop();
}
for (int i = (int)v.size() - 1; i >= 0; i--) {
output(os, v[i]);
if (i != 0) os << ", ";
}
os << "]";
}
template <class OStream,
class Key,
class Compare,
class Allocator,
is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::set<Key, Compare, Allocator> &s) {
os << "{";
std::set<Key, Compare, Allocator> tmp = s;
for (auto it = tmp.begin(); it != tmp.end(); ++it) {
output(os, *it);
if (std::next(it) != tmp.end()) os << ", ";
}
os << "}";
}
template <class OStream,
class Key,
class Compare,
class Allocator,
is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::multiset<Key, Compare, Allocator> &s) {
os << "{";
std::multiset<Key, Compare, Allocator> tmp = s;
for (auto it = tmp.begin(); it != tmp.end(); ++it) {
output(os, *it);
if (std::next(it) != tmp.end()) os << ", ";
}
os << "}";
}
template <class OStream,
class Key,
class Hash,
class KeyEqual,
class Allocator,
is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::unordered_set<Key, Hash, KeyEqual, Allocator> &s) {
os << "{";
std::unordered_set<Key, Hash, KeyEqual, Allocator> tmp = s;
for (auto it = tmp.begin(); it != tmp.end(); ++it) {
output(os, *it);
if (std::next(it) != tmp.end()) os << ", ";
}
os << "}";
}
template <class OStream,
class Key,
class Hash,
class KeyEqual,
class Allocator,
is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::unordered_multiset<Key, Hash, KeyEqual, Allocator> &s) {
os << "{";
std::unordered_multiset<Key, Hash, KeyEqual, Allocator> tmp = s;
for (auto it = tmp.begin(); it != tmp.end(); ++it) {
output(os, *it);
if (std::next(it) != tmp.end()) os << ", ";
}
os << "}";
}
template <class OStream,
class Key,
class T,
class Compare,
class Allocator,
is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::map<Key, T, Compare, Allocator> &m) {
os << "{";
std::map<Key, T, Compare, Allocator> tmp = m;
for (auto it = tmp.begin(); it != tmp.end(); ++it) {
output(os, it->first);
os << ": ";
output(os, it->second);
if (std::next(it) != tmp.end()) os << ", ";
}
os << "}";
}
template <class OStream,
class Key,
class T,
class Hash,
class KeyEqual,
class Allocator,
is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const std::unordered_map<Key, T, Hash, KeyEqual, Allocator> &m) {
os << "{";
std::unordered_map<Key, T, Hash, KeyEqual, Allocator> tmp = m;
for (auto it = tmp.begin(); it != tmp.end(); ++it) {
output(os, it->first);
os << ": ";
output(os, it->second);
if (std::next(it) != tmp.end()) os << ", ";
}
os << "}";
}
template <class OStream, class T, class... Args, is_ostream_t<OStream> * = nullptr>
void output(OStream &os, const T &t, const Args &...args) {
output(os, t);
os << ' ';
output(os, args...);
}
template <class OStream, is_ostream_t<OStream> * = nullptr> void outputln(OStream &os) {
os << '\n';
os.flush();
}
template <class OStream, class T, class... Args, is_ostream_t<OStream> * = nullptr>
void outputln(OStream &os, const T &t, const Args &...args) {
output(os, t, args...);
os << '\n';
os.flush();
}
#else
template <class OStream, class... Args, is_ostream_t<OStream> * = nullptr>
void output(OStream &, const Args &...) {
}
template <class OStream, class... Args, is_ostream_t<OStream> * = nullptr>
void outputln(OStream &, const Args &...) {
}
#endif // KK2
} // namespace debug
} // namespace kk2
#endif // KK2_TEMPLATE_DEBUG_HPP
#ifndef KK2_GEOMETRY_POINT_HPP
#define KK2_GEOMETRY_POINT_HPP 1
namespace kk2 {
template <typename T> struct Point {
static long double PI;
T x, y;
Point(T x = 0, T y = 0) : x(x), y(y) {}
bool operator<(const Point &p) const { return x != p.x ? x < p.x : y < p.y; }
bool operator<=(const Point &p) const { return x != p.x ? x < p.x : y <= p.y; }
bool operator>(const Point &p) const { return x != p.x ? x > p.x : y > p.y; }
bool operator>=(const Point &p) const { return x != p.x ? x > p.x : y >= p.y; }
bool operator==(const Point &p) const { return x == p.x && y == p.y; }
bool operator!=(const Point &p) const { return x != p.x || y != p.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*=(T k) {
x *= k;
y *= k;
return *this;
}
Point &operator/=(T k) {
x /= k;
y /= k;
return *this;
}
Point operator+(const Point &p) const { return Point(*this) += p; }
Point operator-(const Point &p) const { return Point(*this) -= p; }
Point operator*(T k) const { return Point(*this) *= k; }
Point operator/(T k) const { return Point(*this) /= k; }
T dot(const Point &p) const { return x * p.x + y * p.y; }
T cross(const Point &p) const { return x * p.y - y * p.x; }
T cross(const Point &p, const Point &O) const { return (*this - O).cross(p - O); }
T norm() const { return x * x + y * y; }
T norm(const Point &p) const { return (p - *this).norm(); }
long double abs() const { return sqrt(norm()); }
long double dist(const Point &p) const { return (p - *this).abs(); }
long double argument() const { return atan2(y, x); }
// this -> p
long double argument(const Point &p) const {
long double res = p.argument() - argument();
if (res < -PI) res += 2 * PI;
if (res > PI) res -= 2 * PI;
return res;
}
long double argument(const Point &p, const Point &O) const {
return (*this - O).argument(p - O);
}
Point inplace_rotate90() {
std::swap(x, y);
x = -x;
return *this;
}
Point inplace_rotate90(const Point &O) {
*this -= O;
inplace_rotate90();
return *this += O;
}
Point rotate90() const { return Point(-y, x); }
Point rotate90(Point O) const { return (*this - O).rotate90() + O; }
Point inplace_rotate180() {
x = -x;
y = -y;
return *this;
}
Point inplace_rotate180(const Point &O) {
*this -= O;
inplace_rotate180();
return *this += O;
}
Point rotate180() const { return Point(-x, -y); }
Point rotate180(const Point &O) const { return (*this - O).rotate180() + O; }
Point inplace_rotate270() {
std::swap(x, y);
y = -y;
return *this;
}
Point inplace_rotate270(const Point &O) {
*this -= O;
inplace_rotate270();
return *this += O;
}
Point rotate270() const { return Point(y, -x); }
Point rotate270(const Point &O) const { return (*this - O).rotate270() + O; }
friend T dot(const Point &p, const Point &q) { return p.dot(q); }
friend T cross(const Point &p, const Point &q) { return p.cross(q); }
friend T cross(const Point &p, const Point &q, const Point &O) { return p.cross(q, O); }
friend T norm(const Point &p) { return p.norm(); }
friend T norm(const Point &p, const Point &q) { return p.norm(q); }
friend long double abs(const Point &p) { return p.abs(); }
friend long double dist(const Point &p, const Point &q) { return (p - q).abs(); }
friend long double argument(const Point &p) { return p.argument(); }
friend long double argument(const Point &p, const Point &q) { return p.argument(q); }
friend long double argument(const Point &p, const Point &q, const Point &O) {
return p.argument(q, O);
}
friend Point rotate90(const Point &p) { return p.rotate90(); }
friend Point rotate90(const Point &p, const Point &O) { return p.rotate90(O); }
friend Point rotate180(const Point &p) { return p.rotate180(); }
friend Point rotate180(const Point &p, const Point &O) { return p.rotate180(O); }
friend Point rotate270(const Point &p) { return p.rotate270(); }
friend Point rotate270(const Point &p, const Point &O) { return p.rotate270(O); }
template <class OStream, is_ostream_t<OStream> * = nullptr>
friend OStream &operator<<(OStream &os, const Point &p) {
return os << p.x << " " << p.y;
}
template <class IStream, is_istream_t<IStream> * = nullptr>
friend IStream &operator>>(IStream &is, Point &p) {
return is >> p.x >> p.y;
}
};
template <typename T> long double Point<T>::PI = std::acos(-1.0);
} // namespace kk2
#endif // KK2_GEOMETRY_POINT_HPP
#ifndef KK2_RANDOM_GEN_HPP
#define KK2_RANDOM_GEN_HPP 1
#ifndef KK2_RANDOM_SEED_HPP
#define KK2_RANDOM_SEED_HPP 1
namespace kk2 {
namespace random {
using u64 = unsigned long long;
inline u64 non_deterministic_seed() {
u64 seed = std::chrono::duration_cast<std::chrono::nanoseconds>(
std::chrono::high_resolution_clock::now().time_since_epoch())
.count();
seed ^= reinterpret_cast<u64>(&seed);
seed ^= seed << 5;
seed ^= seed >> 41;
seed ^= seed << 20;
return seed;
}
inline u64 deterministic_seed() {
return 5801799128519729247ull;
}
inline u64 seed() {
#if defined(KK2_RANDOM_DETERMINISTIC)
return deterministic_seed();
#else
return non_deterministic_seed();
#endif
}
} // namespace random
} // namespace kk2
#endif // KK2_RANDOM_SEED_HPP
namespace kk2 {
namespace random {
using i64 = long long;
using u64 = unsigned long long;
inline u64 rng() {
static std::mt19937_64 mt(kk2::random::seed());
return mt();
}
// [l, r)
inline i64 rng(i64 l, i64 r) {
assert(l < r);
return l + rng() % (r - l);
}
// [l, r)
template <class T> std::vector<T> random_vector(int n, T l, T r) {
std::vector<T> res(n);
for (int i = 0; i < n; i++) res[i] = rng(l, r);
return res;
}
// [l, r)
std::vector<i64> distinct_rng(i64 l, i64 r, i64 n) {
assert(l < r and n <= r - l);
std::unordered_set<i64> st;
for (i64 i = n; i; --i) {
i64 m = rng(l, r + 1 - i);
if (st.find(m) != st.end()) m = r - i;
st.insert(m);
}
std::vector<i64> res(st.begin(), st.end());
std::sort(res.begin(), res.end());
return res;
}
template <class Iter> void shuffle(Iter first, Iter last) {
if (first == last) return;
int len = 1;
for (auto it = first + 1; it != last; ++it) {
len++;
int j = rng(0, len);
if (j != len - 1) std::iter_swap(first + j, it);
}
}
template <class T> std::vector<T> perm(int n) {
std::vector<T> res(n);
std::iota(res.begin(), res.end(), T(0));
shuffle(res.begin(), res.end());
return res;
}
template <class T> std::vector<T> choices(int l, int r, int k) {
assert(l < r and k <= r - l);
std::vector<T> res(r - l);
std::iota(res.begin(), res.end(), T(l));
shuffle(res.begin(), res.end());
res.resize(k);
return res;
}
} // namespace random
} // namespace kk2
#endif // KK2_RANDOM_GEN_HPP
using namespace std;
void solve() {
/*
縦線でだいたい分けて，すこしだけ傾ければ良い
|a|, |b| <= 10^5
がとても厳しい
傾きを適当にとってきて，
半分を目指す．
直線の上側か下側かを見ればカウントができる
普通に符号をみればよい
傾きの種類は，
m = 1e5
2 * \sum_{n=1}^{m} \floor(m / n) * \phi(n)
> 10^10
*/
int n;
kin >> n;
vc<kk2::Point<int>> p(2 * n);
kin >> p;
sort(all(p));
constexpr int m = 1e5;
auto count = [&](i64 a, i64 b, i64 c) -> array<int, 3> {
// y = (a / b)x + c / b
int count_up = 0, count_down = 0, count_on = 0;
rep (i, 2 * n) {
i64 l = b * p[i].y;
i64 r = a * p[i].x + c;
if (l > r) count_up++;
else if (l < r) count_down++;
else count_on++;
}
return {count_up, count_down, count_on};
};
while (true) {
int b = kk2::random::rng(1, m + 1), a = kk2::random::rng(0, m + 1);
// int b = 3, a = 1;
int g = gcd(a, b);
a /= g, b /= g;
// kk2::debug::outputln(kout, a, b);
i64 ok = i64(-2e10), ng = i64(2e10);
while (ng - ok > 1) {
i64 mid = (ok + ng) / 2;
auto [count_up, count_down, count_on] = count(a, b, mid);
if (count_up == n and count_down == n) {
ok = mid;
break;
}
if (count_up >= n) ok = mid;
else ng = mid;
}
auto [count_up, count_down, count_on] = count(a, b, ok);
// kout << ok << kendl;
if (count_up == n and count_down == n) {
kout << -a << " " << b << " " << -ok << kendl;
return;
} else continue;
}
}
int main() {
int t = 1;
// kin >> t;
rep (t) solve();
return 0;
}
// Author: kk2
// converted by https://github.com/kk2a/cpp-bundle
// 2025-03-31 06:36:37