提出 #372963

---

ソースコード 拡げる

#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>
#include <array>
#include <climits>
#include <bitset>
#include <cassert>
#include <unordered_map>
#include <complex>

#ifdef _MSC_VER
#include <agents.h>
#endif

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define UNIQUE(v) (v).erase(unique(ALL(v)), (v).end())
#define MP make_pair
#define MT make_tuple

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;

class bipartite_graph{
	vector<vector<int> > Graph;
	vector<int> used, match;
	int V;
public:
	bipartite_graph(int size) :V(size){
		Graph.resize(V);
		used.resize(V, 0);
		match.resize(V, -1);
	}
	void add_edge(int from, int to){
		Graph[from].push_back(to);
		Graph[to].push_back(from);
	}
	int dfs(int v){
		used[v] = 1;
		for (int i = 0; i < Graph[v].size(); i++){
			int x = Graph[v][i], w = match[x];
			if (w < 0 || !used[w] && dfs(w)){
				match[x] = v;
				match[v] = x;
				return 1;
			}
		}
		return 0;
	}
	int matching(){
		fill(match.begin(), match.end(), -1);
		int res = 0;
		for (int v = 0; v < V; v++){
			if (match[v] >= 0) continue;
			fill(used.begin(), used.end(), 0);
			if (dfs(v)) res++;
		}
		return res;
	}
};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout.setf(ios::fixed);
	cout.precision(20);

	int m;
	cin >> m;
	vector<int> px(m), py(m), s(m), t(m);
	rep(i, m){
		cin >> px[i] >> py[i];
	}
	int n;
	cin >> n;
	px.resize(m + n);
	py.resize(m + n);
	s.resize(m + n);
	t.resize(m + n);
	FOR(i, m, m + n){
		cin >> px[i] >> py[i] >> s[i] >> t[i];
	}

	int k = m + n;
	bipartite_graph G(k*2);

	auto check = [&](int a, int b){
		int dsq = (px[a] - px[b]) * (px[a] - px[b]) + (py[a] - py[b])*(py[a] - py[b]);
		return dsq <= (s[b] - t[a])*(s[b] - t[a]);
	};

	rep(i, k) FOR(j, i + 1, k){
		if (j >= m && check(i, j)){
			G.add_edge(i, j + k);
		}
	}

	//cout << k - G.matching() << endl;

	cout << (k - G.matching() <= m ? "YES" : "NO") << endl;
}

提出情報

ジャッジ結果