結果
問題 | No.2436 Min Diff Distance |
ユーザー |
![]() |
提出日時 | 2023-08-19 00:00:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 353 ms / 2,000 ms |
コード長 | 5,179 bytes |
コンパイル時間 | 1,511 ms |
コンパイル使用メモリ | 139,072 KB |
最終ジャッジ日時 | 2025-02-16 11:06:25 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#ifndef LOCAL#define FAST_IO#endif// ============#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <cmath>#include <iomanip>#include <iostream>#include <list>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <tuple>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>#define OVERRIDE(a, b, c, d, ...) d#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)#define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)#define ALL(x) begin(x), end(x)using namespace std;using u32 = unsigned int;using u64 = unsigned long long;using i32 = signed int;using i64 = signed long long;using f64 = double;using f80 = long double;template <typename T>using Vec = vector<T>;template <typename T>bool chmin(T &x, const T &y) {if (x > y) {x = y;return true;}return false;}template <typename T>bool chmax(T &x, const T &y) {if (x < y) {x = y;return true;}return false;}#ifdef INT128using u128 = __uint128_t;using i128 = __int128_t;istream &operator>>(istream &is, i128 &x) {i64 v;is >> v;x = v;return is;}ostream &operator<<(ostream &os, i128 x) {os << (i64)x;return os;}istream &operator>>(istream &is, u128 &x) {u64 v;is >> v;x = v;return is;}ostream &operator<<(ostream &os, u128 x) {os << (u64)x;return os;}#endif[[maybe_unused]] constexpr i32 INF = 1000000100;[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;struct SetUpIO {SetUpIO() {#ifdef FAST_IOios::sync_with_stdio(false);cin.tie(nullptr);#endifcout << fixed << setprecision(15);}} set_up_io;// ============#ifdef DEBUGF#else#define DBG(x) (void)0#endif#line 2 "graph/mst/manhattan-mst.hpp"#line 2 "graph/graph-template.hpp"// https://ei1333.github.io/library/graph/mst/manhattan-mst.hpp/*** @brief Graph Template(グラフテンプレート)*/template< typename T = int >struct Edge {int from, to;T cost;int idx;Edge() = default;Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {}operator int() const { return to; }};template< typename T = int >struct Graph {vector< vector< Edge< T > > > g;int es;Graph() = default;explicit Graph(int n) : g(n), es(0) {}size_t size() const {return g.size();}void add_directed_edge(int from, int to, T cost = 1) {g[from].emplace_back(from, to, cost, es++);}void add_edge(int from, int to, T cost = 1) {g[from].emplace_back(from, to, cost, es);g[to].emplace_back(to, from, cost, es++);}void read(int M, int padding = -1, bool weighted = false, bool directed = false) {for(int i = 0; i < M; i++) {int a, b;cin >> a >> b;a += padding;b += padding;T c = T(1);if(weighted) cin >> c;if(directed) add_directed_edge(a, b, c);else add_edge(a, b, c);}}inline vector< Edge< T > > &operator[](const int &k) {return g[k];}inline const vector< Edge< T > > &operator[](const int &k) const {return g[k];}};template< typename T = int >using Edges = vector< Edge< T > >;#line 4 "graph/mst/manhattan-mst.hpp"/*** @brief Manhattan MST*/template< typename T >Edges< T > manhattan_mst(vector< T > xs, vector< T > ys) {assert(xs.size() == ys.size());Edges< T > ret;int n = (int) xs.size();vector< int > ord(n);iota(ord.begin(), ord.end(), 0);for(int s = 0; s < 2; s++) {for(int t = 0; t < 2; t++) {auto cmp = [&](int i, int j) -> bool {return xs[i] + ys[i] < xs[j] + ys[j];};sort(ord.begin(), ord.end(), cmp);map< T, int > idx;for(int i:ord) {for(auto it = idx.lower_bound(-ys[i]);it != idx.end(); it = idx.erase(it)) {int j = it->second;if(xs[i] - xs[j] < ys[i] - ys[j]) break;ret.emplace_back(i, j, abs(xs[i] - xs[j]) + abs(ys[i] - ys[j]));}idx[-ys[i]] = i;}swap(xs, ys);}for(int i = 0; i < n; i++) xs[i] *= -1;}return ret;}int main() {i32 n;cin >> n;Vec<i32> x(n), y(n);REP(i, n) {cin >> x[i] >> y[i];}auto es = manhattan_mst(x, y);REP(i, n) {i32 a = x[i], b = y[i];x[i] = a + b;y[i] = a - b;}i32 xmn = INF, xmx = -INF, ymn = INF, ymx = -INF;REP(i, n) {chmin(xmn, x[i]);chmax(xmx, x[i]);chmin(ymn, y[i]);chmax(ymx, y[i]);}Vec<i32> mx(n, 0);REP(i, n) {mx[i] = max({x[i] - xmn, xmx - x[i], y[i] - ymn, ymx - y[i]});}Vec<i32> mn(n, INF);for (auto e : es) {chmin(mn[e.from], e.cost);chmin(mn[e.to], e.cost);}i32 ans = INF;REP(i, n) {chmin(ans, mx[i] - mn[i]);}cout << ans << '\n';}