提出 #372689

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
struct edge {int to,cap,rev;};
const int MAX_V=3000;
int V;				//substitute!!
vector<int> G[MAX_V];
int match[MAX_V];
bool used[MAX_V];
void add_edge(int u,int v){
//	show(u);
//	show(v);
	u=u*2,v=v*2+1;
	G[u].push_back(v);
	G[v].push_back(u);
}
bool dfs(int v){
	used[v]=true;
	rep(i,G[v].size()){
		int u=G[v][i],w=match[u];
		if(w<0 || (!used[w] && dfs(w))){
			match[v]=u;
			match[u]=v;
			return true;
		}
	}
	return false;
}
int nibu(){
	int res=0;
	memset(match,-1,sizeof(match));
	rep(v,V){
		if(match[v]<0){
			memset(used,0,sizeof(used));
			if(dfs(v)) res++;
		}
	}
	return res;
}
int x[1003],y[1003],s[1003],t[1003];
bool isedge[1003][1003];
int main(){
	int m;
	cin>>m;
	rep(i,m) cin>>x[i]>>y[i];
	int n;
	cin>>n;
	rep(i,n) cin>>x[i+m]>>y[i+m]>>s[i+m]>>t[i+m];
	V=(m+n+3)*2;
	rep(i,n+m) rep(j,n+m) if(i!=j&&!(i<m&&j<m)&&t[i]<=s[j]) {
		int dis=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
		if(dis<=(s[j]-t[i])*(s[j]-t[i])){
			add_edge(i,j);
//			isedge[i][j]=1;
		}
	}
/*	int ss=n+m;
	rep(i,m){
		add_edge(ss,i);
	}
	rep(i,n){
		bool ok=0;
		rep(j,m) if(isedge[j+n][i]) ok=1;
		if(ok) add_edge(ss,m+i);
	}*/
	int tmp=nibu();
//	show(tmp);
	int ans=n+m-tmp;
//	show(ans);
	if(ans<=m) puts("YES");
	else puts("NO");
}

提出情報

ジャッジ結果