結果
| 問題 |
No.2897 ２集合間距離
|
| コンテスト | |
| ユーザー |
 矢澤式WINTER
|
| 提出日時 | 2024-09-20 22:55:12 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 639 ms / 3,500 ms |
| コード長 | 19,732 bytes |
| コンパイル時間 | 6,590 ms |
| コンパイル使用メモリ | 337,444 KB |
| 実行使用メモリ | 121,300 KB |
| 最終ジャッジ日時 | 2024-09-20 22:55:26 |
| 合計ジャッジ時間 | 12,633 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 24 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
//*/
#include <atcoder/all>
using namespace atcoder;
// //*/
// #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define ALL(x) (x).begin(),(x).end()
#define dbgv(x); for(auto now : x) cout << now << " "; cout << endl;
//using p = pair<int,int>;
using ll = long long;
using ull = unsigned long long;
//*/
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vint;
random_device rnd;
mt19937 rng(rnd());
namespace nachia{
template<class Int = long long, class Int2 = long long>
struct VecI2 {
Int x, y;
VecI2() : x(0), y(0) {}
VecI2(std::pair<Int, Int> _p) : x(std::move(_p.first)), y(std::move(_p.second)) {}
VecI2(Int _x, Int _y) : x(std::move(_x)), y(std::move(_y)) {}
VecI2& operator+=(VecI2 r){ x+=r.x; y+=r.y; return *this; }
VecI2& operator-=(VecI2 r){ x-=r.x; y-=r.y; return *this; }
VecI2& operator*=(Int r){ x*=r; y*=r; return *this; }
VecI2 operator+(VecI2 r) const { return VecI2(x+r.x, y+r.y); }
VecI2 operator-(VecI2 r) const { return VecI2(x-r.x, y-r.y); }
VecI2 operator*(Int r) const { return VecI2(x*r, y*r); }
VecI2 operator-() const { return VecI2(-x, -y); }
Int2 operator*(VecI2 r) const { return Int2(x) * Int2(r.x) + Int2(y) * Int2(r.y); }
Int2 operator^(VecI2 r) const { return Int2(x) * Int2(r.y) - Int2(y) * Int2(r.x); }
bool operator<(VecI2 r) const { return x < r.x || (!(r.x < x) && y < r.y); }
Int2 norm() const { return Int2(x) * Int2(x) + Int2(y) * Int2(y); }
static bool compareYX(VecI2 a, VecI2 b){ return a.y < b.y || (!(b.y < a.y) && a.x < b.x); }
static bool compareXY(VecI2 a, VecI2 b){ return a.x < b.x || (!(b.x < a.x) && a.y < b.y); }
bool operator==(VecI2 r) const { return x == r.x && y == r.y; }
bool operator!=(VecI2 r) const { return x != r.x || y != r.y; }
};
} // namespace nachia
namespace nachia{
template<class Elem>
class CsrArray{
public:
struct ListRange{
using iterator = typename std::vector<Elem>::iterator;
iterator begi, endi;
iterator begin() const { return begi; }
iterator end() const { return endi; }
int size() const { return (int)std::distance(begi, endi); }
Elem& operator[](int i) const { return begi[i]; }
};
struct ConstListRange{
using iterator = typename std::vector<Elem>::const_iterator;
iterator begi, endi;
iterator begin() const { return begi; }
iterator end() const { return endi; }
int size() const { return (int)std::distance(begi, endi); }
const Elem& operator[](int i) const { return begi[i]; }
};
private:
int m_n;
std::vector<Elem> m_list;
std::vector<int> m_pos;
public:
CsrArray() : m_n(0), m_list(), m_pos() {}
static CsrArray Construct(int n, std::vector<std::pair<int, Elem>> items){
CsrArray res;
res.m_n = n;
std::vector<int> buf(n+1, 0);
for(auto& [u,v] : items){ ++buf[u]; }
for(int i=1; i<=n; i++) buf[i] += buf[i-1];
res.m_list.resize(buf[n]);
for(int i=(int)items.size()-1; i>=0; i--){
res.m_list[--buf[items[i].first]] = std::move(items[i].second);
}
res.m_pos = std::move(buf);
return res;
}
static CsrArray FromRaw(std::vector<Elem> list, std::vector<int> pos){
CsrArray res;
res.m_n = pos.size() - 1;
res.m_list = std::move(list);
res.m_pos = std::move(pos);
return res;
}
ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; }
ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; }
int size() const { return m_n; }
int fullSize() const { return (int)m_list.size(); }
};
} // namespace nachia
namespace nachia{
// Int3 must be able to handle the value range :
// |x| <= | (any input - any input) ** 4 * 12 |
template<class Int = long long, class Int2 = long long, class Int3 = Int2>
class DelaunayTriangulation {
public:
using GPos2 = VecI2<Int, Int2>;
struct Circumcenter {
Int3 x; Int3 y; Int2 d;
static Circumcenter From3Points(GPos2 p1, GPos2 p2, GPos2 p3){
GPos2 dp1 = p2 - p1;
GPos2 dp2 = p3 - p1;
Int2 d1 = dp1.norm(); Int2 d2 = dp2.norm();
Int2 w = dp1 ^ dp2; w += w;
Int3 px = (Int3(dp2.y) * Int3(d1) - Int3(dp1.y) * Int3(d2)) + Int3(w) * Int3(p1.x);
Int3 py = (Int3(dp1.x) * Int3(d2) - Int3(dp2.x) * Int3(d1)) + Int3(w) * Int3(p1.y);
return { px, py, w };
}
};
struct Edge {
int to;
int ccw;
int cw;
int rev;
bool enabled = false;
};
private:
static int isDinOABC(GPos2 a, GPos2 b, GPos2 c, GPos2 d){
a = a - d;
b = b - d;
c = c - d;
auto val = Int3(b^c) * Int3(a.norm()) + Int3(c^a) * Int3(b.norm()) + Int3(a^b) * Int3(c.norm());
return val > Int3(0) ? 1 : 0;
}
int getOpenAddress(){
if(openAddress.empty()){
edges.push_back({});
return (int)edges.size() - 1;
}
int res = openAddress.back();
openAddress.pop_back();
return res;
}
std::pair<int, int> newEdge(int u, int v){
int euv = getOpenAddress();
int evu = getOpenAddress();
edges[euv].ccw = edges[euv].cw = euv;
edges[evu].ccw = edges[evu].cw = evu;
edges[euv].to = v;
edges[evu].to = u;
edges[euv].rev = evu;
edges[evu].rev = euv;
edges[euv].enabled = true;
edges[evu].enabled = true;
return { euv, evu };
}
void eraseSingleEdge(int e){
int eccw = edges[e].ccw;
int ecw = edges[e].cw;
edges[eccw].cw = ecw;
edges[ecw].ccw = eccw;
edges[e].enabled = false;
}
void eraseEdgeBidirectional(int e){
int ex = edges[e].rev;
eraseSingleEdge(e);
eraseSingleEdge(ex);
openAddress.push_back(e);
openAddress.push_back(ex);
}
void insertCcwAfter(int e, int x){
int xccw = edges[x].ccw;
edges[e].ccw = xccw;
edges[xccw].cw = e;
edges[e].cw = x;
edges[x].ccw = e;
}
void insertCwAfter(int e, int x){
int xcw = edges[x].cw;
edges[e].cw = xcw;
edges[xcw].ccw = e;
edges[e].ccw = x;
edges[x].cw = e;
}
// move from ab to ac ... is this ccw?
int isCcw(int a, int b, int c) const {
auto ab = pos[b] - pos[a];
auto ac = pos[c] - pos[a];
auto cp = ab ^ ac;
if(0 < cp) return 1;
if(cp < 0) return -1;
return 0;
}
std::pair<int, int> goNext(int , int ea){
int ap = edges[ea].to;
int eap = edges[edges[ea].rev].ccw;
return { ap, eap };
}
std::pair<int, int> goPrev(int , int ea){
int ap = edges[edges[ea].cw].to;
int eap = edges[edges[ea].cw].rev;
return { ap, eap };
}
std::tuple<int, int, int, int> goBottom(int a, int ea, int b, int eb){
while(true){
auto [ap, eap] = goPrev(a, ea);
if(isCcw(b, a, ap) > 0){
std::tie(a, ea) = { ap, eap };
continue;
}
auto [bp, ebp] = goNext(b, eb);
if(isCcw(a, b, bp) < 0){
std::tie(b, eb) = { bp, ebp };
continue;
}
break;
}
return { a, ea, b, eb };
}
std::pair<int, int> getMaximum(int a, int ea, bool toMin){
std::pair<int, int> ans = { a, ea };
int p = a, ep = ea;
do {
std::tie(p, ep) = goNext(p, ep);
if(toMin) ans = std::min(ans, std::make_pair(p, ep));
else ans = std::max(ans, std::make_pair(p, ep));
} while(ep != ea);
return ans;
}
bool isDinOABC(int a, int b, int c, int d){
return isDinOABC(pos[a], pos[b], pos[c], pos[d]);
}
std::pair<int, int> dfs(int a, int ea, int b, int eb){
std::tie(a, ea) = getMaximum(a, ea, false);
std::tie(b, eb) = getMaximum(b, eb, true);
auto [al, eal, bl, ebl] = goBottom(a, ea, b, eb);
auto [bu, ebu, au, eau] = goBottom(b, eb, a, ea);
ebl = edges[ebl].cw;
ebu = edges[ebu].cw;
auto [abl, bal] = newEdge(al, bl);
insertCwAfter(abl, eal);
insertCcwAfter(bal, ebl);
if(al == au) eau = abl;
if(bl == bu) ebu = bal;
int ap = al, eap = eal;
int bp = bl, ebp = ebl;
while(ap != au || bp != bu){
int a2 = edges[eap].to;
int b2 = edges[ebp].to;
int nxeap = edges[eap].ccw;
int nxebp = edges[ebp].cw;
if(eap != eau && nxeap != abl){
int a1 = edges[nxeap].to;
if(isDinOABC(ap, bp, a2, a1)){
eraseEdgeBidirectional(eap);
eap = nxeap;
continue;
}
}
if(ebp != ebu && nxebp != bal){
int b1 = edges[nxebp].to;
if(isDinOABC(b2, ap, bp, b1)){
eraseEdgeBidirectional(ebp);
ebp = nxebp;
continue;
}
}
bool chooseA = ebp == ebu;
if(eap != eau && ebp != ebu){
if(isCcw(ap, bp, b2) < 0) chooseA = true;
else if(isCcw(a2, ap, bp) < 0) chooseA = false;
else chooseA = isDinOABC(ap, bp, b2, a2);
}
if(chooseA){
nxeap = edges[edges[eap].rev].ccw;
auto [hab, hba] = newEdge(a2, bp);
insertCwAfter(hab, nxeap);
insertCcwAfter(hba, ebp);
eap = nxeap; ap = a2;
}
else {
nxebp = edges[edges[ebp].rev].cw;
auto [hba, hab] = newEdge(b2, ap);
insertCcwAfter(hba, nxebp);
insertCwAfter(hab, eap);
ebp = nxebp; bp = b2;
}
}
return { al, abl };
}
std::pair<int, int> solveRange(int l, int r){
if(r - l == 2){
int u = l;
int v = l + 1;
auto [uv, vu] = newEdge(u, v);
return { u, uv };
}
if(r - l == 3){
int u = l;
int v = l + 1;
int w = l + 2;
auto [uv, vu] = newEdge(u, v);
auto [vw, wv] = newEdge(v, w);
int ccw = isCcw(u, v, w);
if(ccw == 0){
insertCcwAfter(vu, vw);
}
if(ccw > 0){
auto [uw, wu] = newEdge(u, w);
insertCwAfter(uv, uw);
insertCwAfter(vw, vu);
insertCwAfter(wu, wv);
return { u, uv };
}
if(ccw < 0){
auto [uw, wu] = newEdge(u, w);
insertCcwAfter(uv, uw);
insertCcwAfter(vw, vu);
insertCcwAfter(wu, wv);
return { v, vu };
}
return { u, uv };
}
int m = (l + r) / 2;
auto [a, ea] = solveRange(l, m);
auto [b, eb] = solveRange(m, r);
return dfs(a, ea, b, eb);
}
void solve(){
int sz = (int)pos.size();
if(sz <= 1) return;
std::vector<int> pi(pos.size());
for(int i=0; i<(int)pi.size(); i++) pi[i] = i;
std::sort(
pi.begin(), pi.end(),
[&](int l, int r){
return pos[l].x != pos[r].x ?
pos[l].x < pos[r].x : pos[l].y < pos[r].y;
}
);
auto posbuf = pos;
int posptr = 0;
mappings.assign(sz, 0);
for(int i=0; i<sz; i++){
int v = pi[i];
if(i == 0 || !(posbuf[pi[posptr-1]] == posbuf[v])){
pi[posptr] = v;
pos[posptr++] = posbuf[v];
mappings[v] = v;
} else {
mappings[v] = pi[posptr-1];
}
}
if(posptr >= 2) outerOneEdge = solveRange(0, posptr).second;
std::swap(pos, posbuf);
for(auto& e : edges) e.to = pi[e.to];
}
std::vector<int> openAddress;
std::vector<GPos2> pos;
std::vector<Edge> edges;
std::vector<int> mappings;
bool voronoiCalculated = false;
int outerOneEdge = -1;
std::vector<Circumcenter> circumcenters;
std::vector<int> voronoiNodeRefLH;
CsrArray<std::pair<int,int>> voronoi;
void solveVoronoiDiagram(){
if(edges.empty()){
voronoi = CsrArray<std::pair<int,int>>::FromRaw({}, std::vector<int>(pos.size()+1, 0));
voronoiCalculated = true;
}
if(voronoiCalculated) return;
int m = edges.size();
std::vector<int> res(m, -1);
int outlineCount = 0;
{
int eu = outerOneEdge;
int es = eu;
do{
eu = edges[eu].rev;
res[eu] = -2;
eu = edges[eu].ccw;
outlineCount++;
} while(es != eu);
}
for(int e=0; e<m; e++) if(res[e] == -1){
int f = edges[edges[e].rev].cw;
int g = edges[edges[f].rev].cw;
int v = edges[e].to;
int w = edges[f].to;
int u = edges[g].to;
int c = circumcenters.size();
circumcenters.push_back(Circumcenter::From3Points(pos[u], pos[v], pos[w]));
res[e] = res[f] = res[g] = c;
}
for(int e=0; e<m; e++) if(res[e] == -2){
int f = edges[e].rev;
int v = edges[e].to;
int u = edges[f].to;
if(res[f] == -2){
int c1 = circumcenters.size();
circumcenters.push_back({
Int2(pos[u].x) + Int2(pos[v].x) + Int2(pos[v].y - pos[u].y),
Int2(pos[u].y) + Int2(pos[v].y) - Int2(pos[v].x - pos[u].x), Int2(2) });
int c2 = circumcenters.size();
circumcenters.push_back({
Int2(pos[u].x) + Int2(pos[v].x) - Int2(pos[v].y - pos[u].y),
Int2(pos[u].y) + Int2(pos[v].y) + Int2(pos[v].x - pos[u].x), Int2(2) });
res[e] = c1;
res[f] = c2;
} else {
int c1 = circumcenters.size();
auto q = circumcenters[res[f]];
auto d = pos[v] - pos[u];
q.x -= Int3(q.d) * Int3(d.y);
q.y += Int3(q.d) * Int3(d.x);
circumcenters.push_back(q);
res[e] = c1;
}
}
voronoiNodeRefLH = std::move(res);
std::vector<int> oneEdge(pos.size(), -1);
for(int e=0; e<m; e++) oneEdge[edges[e].to] = edges[e].rev;
{
std::vector<std::pair<int,int>> res(m*2);
std::vector<int> ptr(pos.size() + 1);
for(int s=0; s<int(pos.size()); s++){
ptr[s+1] = ptr[s];
if(oneEdge[s] >= 0){
int es = oneEdge[s];
int e = es;
do{
int re = edges[e].rev;
res[ptr[s+1]++] = { voronoiNodeRefLH[re], voronoiNodeRefLH[e] };
e = edges[e].ccw;
} while(e != es);
}
}
voronoi = CsrArray<std::pair<int,int>>::FromRaw(std::move(res), std::move(ptr));
}
voronoiCalculated = true;
}
public:
DelaunayTriangulation()
: pos()
{ solve(); }
DelaunayTriangulation(std::vector<GPos2> x_points)
: pos(std::move(x_points))
{
solve();
}
std::vector<std::pair<int, int>> getEdges() const {
std::vector<std::pair<int, int>> res;
for(int e=0; e<(int)edges.size(); e++) if(edges[e].enabled){
int re = edges[e].rev;
if(e < re) continue;
res.push_back({ edges[e].to, edges[re].to });
}
for(int v=0; v<int(mappings.size()); v++){
if(mappings[v] != v) res.push_back({ v, mappings[v] });
}
return res;
}
const std::vector<Circumcenter>& getVirtualCircumcenters(){
solveVoronoiDiagram();
return circumcenters;
}
std::vector<std::pair<double, double>> getVirtualCircumcentersAsDouble(){
solveVoronoiDiagram();
std::vector<std::pair<double, double>> res(circumcenters.size());
for(int i=0; i<int(circumcenters.size()); i++){
res[i].first = double(circumcenters[i].x) / double(circumcenters[i].d);
res[i].second = double(circumcenters[i].y) / double(circumcenters[i].d);
}
return res;
}
const CsrArray<std::pair<int,int>>& getVoronoiDiagram(){
solveVoronoiDiagram();
return voronoi;
}
};
} // namespace nachia
namespace nachia {
struct DsuFast{
private:
std::vector<int> w;
public:
DsuFast(int n = 0) : w(n, -1) {}
int leader(int u){
if(w[u] < 0) return u;
return w[u] = leader(w[u]);
}
int operator[](int u){ return leader(u); }
int merge(int u, int v){
u = leader(u);
v = leader(v);
if(u == v) return u;
if(-w[u] < -w[v]) std::swap(u, v);
w[u] += w[v];
w[v] = u;
return u;
}
int size(int u){ return -w[leader(u)]; }
bool same(int u, int v){ return leader(u) == leader(v); }
};
} // namespace nachia
void solve(){
int n,m;
cin >> n;
using i64 = long long;
using Point = nachia::VecI2<i64, i64>;
vector<i64> xa(n),ya(n);
rep(i,n) cin >> xa[i] >> ya[i];
cin >> m;
vector<i64> xb(m),yb(m);
rep(i,m) cin >> xb[i] >> yb[i];
vector<i64> x(n+m),y(n+m);
rep(i,n){
x[i] = xa[i];
y[i] = ya[i];
}
rep(i,m){
x[i+n] = xb[i];
y[i+n] = yb[i];
}
std::vector<Point> A(n+m);
rep(i,n+m){
A[i].x = x[i];
A[i].y = y[i];
}
auto weight = [&](std::pair<int,int> p){ return (abs(A[p.first].x - A[p.second].x)+abs(A[p.first].y - A[p.second].y)); };
auto tri = nachia::DelaunayTriangulation(A).getEdges();
std::sort(tri.begin(), tri.end(),
[&](std::pair<int,int> l, std::pair<int,int> r) -> bool {
return weight(l) < weight(r); });
auto dsu = nachia::DsuFast(n+m);
std::vector<std::pair<int,int>> ans;
for(auto a : tri){
if(dsu.same(a.first, a.second)) continue;
dsu.merge(a.first, a.second);
if(a.first > a.second) std::swap(a.first, a.second);
ans.push_back(a);
}
std::sort(ans.begin(), ans.end());
ll anser = 1e9;
cerr << ans.size() << endl;
for(auto a : ans)if((a.first >= n && a.second < n) || (a.first < n && a.second >= n)){
ll now = abs(A[a.first].x - A[a.second].x)+abs(A[a.first].y - A[a.second].y);
chmin(anser,now);
}
cout << anser << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1; //cin >> t;
rep(testcase,t) solve();
}