Submission #372967

---

Source Code Expand

//#define NDEBUG

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <cassert>
#include <numeric>
#include <cstdio>
#include <complex>

using namespace std;
typedef long long ll;
typedef long double D;

/**
 * Dinic法による最大流
 *
 * ほとんど蟻本そのまま
 * template引数のint Vは頂点数
 */
template<int V>
struct MaxFlow {
    using T = int; /// 辺の重みの型
    const T INF = 1<<28;
    struct Edge {
        int to, rev;
        T cap;
    };
    vector<Edge> g[V];
    int level[V];
    int iter[V];
    /// 初期化
    void init() {
        for (int i = 0; i < V; i++) {
            g[i].clear();
        }
    }
    /// 有向辺の追加
    void add(int from, int to, T cap) {
        assert(0 <= from && from < V);
        assert(0 <= to && to < V);
        assert(from != to);
        g[from].push_back(Edge{to, (int)g[to].size(), cap});
        g[to].push_back(Edge{from, (int)g[from].size()-1, 0});
    }
    /// 無向辺の追加
    void add_multi(int from, int to, T cap) {
        g[from].push_back(Edge{to, (int)g[to].size(), cap});
        g[to].push_back(Edge{from, (int)g[from].size()-1, cap});
    }

    void bfs(int s) {
        fill_n(level, V, -1);
        queue<int> que;
        level[s] = 0;
        que.push(s);
        while (!que.empty()) {
            int v = que.front(); que.pop();
            for (Edge e: g[v]) {
                if (e.cap <= 0) continue;
                if (level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }

    T dfs(int v, int t, T f) {
        if (v == t) return f;
        for (int &i = iter[v]; i < (int)g[v].size(); i++) {
            Edge &e = g[v][i];
            if (e.cap <= 0) continue;
            if (level[v] < level[e.to]) {
                T d = dfs(e.to, t, min(f, e.cap));
                if (d <= 0) continue;
                e.cap -= d;
                g[e.to][e.rev].cap += d;
                return d;
            }
        }
        return 0;
    }

    // sからtへの最大流を返す
    T exec(int s, int t) {
        T flow = 0;
        while (true) {
            bfs(s);
            if (level[t] < 0) return flow;
            fill_n(iter, V, 0);
            T f;
            while ((f = dfs(s, t, INF)) > 0) {
                flow += f;
            }
        }
    }
};

typedef long double R;
typedef complex<R> P;

const R EPS = 1e-10;
const R PI = acos((R)(-1));

/*
 -1 -> neg
  0 -> near 0
  1 -> pos
  */
int sgn(R a) {
    if (a < -EPS) return -1;
    if (a > EPS) return 1;
    return 0;
}

int sgn(R a, R b) {
    return sgn(b-a);
}

P yubi[3];
MaxFlow<3000> mf;
P note[1010];
int sn[1010], tn[1010];
int main() {
    mf.init();
    int m;
    cin >> m;
    //0..m yubi
    //10..n+10 note
    //1100 start 1101 end
    //1500 offset
    int sv = 1100, ev = 1101, off = 1500;
    for (int i = 0; i < m; i++) {
        R x, y;
        cin >> x >> y;
        yubi[i] = P(x, y);
        mf.add(sv, i, 1);
        mf.add(i+off, ev, 1);
    }

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        R x, y;
        cin >> x >> y >> sn[i] >> tn[i];
        note[i] = P(x, y);
        mf.add(sv, i+10, 1);
        mf.add(i+off+10, ev, 1);
        for (int j = 0; j < m; j++) {
            if (sgn(abs(yubi[j]-note[i]), sn[i]) != -1) {
                mf.add(j, i+off+10, 1);
            }
        }
        for (int j = 0; j < i; j++) {
            assert(sn[i]-tn[j] >= 0);
            if (sgn(abs(note[j]-note[i]), sn[i]-tn[j]) != -1) {
                mf.add(j+10, i+off+10, 1);
            }
        }
    }
    if (m+n - mf.exec(sv, ev) <= m) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

Submission Info

Judge Result