#1012364 (C++23) No.2897 ２集合間距離

提出ソース
結果

問題	No.2897 ２集合間距離
ユーザー	矢澤式WINTER
提出日時	2024-09-20 22:55:12
言語	C++23 (gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	3 ms 6,940 KB
testcase_13	AC	5 ms 6,940 KB
testcase_14	AC	18 ms 7,068 KB
testcase_15	AC	31 ms 7,968 KB
testcase_16	AC	598 ms 121,300 KB
testcase_17	AC	617 ms 121,116 KB
testcase_18	AC	601 ms 119,908 KB
testcase_19	AC	639 ms 120,744 KB
testcase_20	AC	601 ms 119,944 KB
testcase_21	AC	627 ms 120,772 KB
testcase_22	AC	569 ms 120,892 KB
testcase_23	AC	598 ms 121,036 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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();
}
yukicoder

結果

テストケース

ソースコード
