记录编号	288718	评测结果	AAAAAAAAAA
题目名称	[CTSC 2000] 丘比特的烦恼	最终得分	100
用户昵称	甘罗	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2016-08-03 14:48:59	内存使用	0.35 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

int i,k,n,j,p,g;
int bx[110],by[110],gx[110],gy[110];
int w[110][110]={0},lx[110]={-1},ly[110]={0},l[110],s[110];
char bn[110][25],gn[110][25];
char x[25],y[25];
int vx[110],vy[110];

inline int max(int a,int b){return (a>b)?a:b;}

inline void Change_Char(){
	int i=0,j=0;
	for (i=1;i<=n;i++){
		for (j=0;j<strlen(bn[i]);j++)
		if (bn[i][j]<97)	bn[i][j]+=32;
		for (j=0;j<strlen(gn[i]);j++)
		if (gn[i][j]<97)	gn[i][j]+=32;
	}
	return;
}

inline void Change(){
	int i=0;
	for (i=0;i<strlen(x);i++)	if (x[i]<97)	x[i]+=32;
	for (i=0;i<strlen(y);i++)	if (y[i]<97)	y[i]+=32;
	return;
}

inline bool Gx(int x1,int y1,int x2,int y2,int x3,int y3){
	if ((x1-x3)*(y2-y3)!=(x2-x3)*(y1-y3))	return false;
	else if (y1==y2)	return ((x1-x3)*(x2-x3)<0);
	else return ((y1-y3)*(y2-y3)<0);
}

inline bool Check(int B,int G){
	int i=0,j=0;
	if (sqrt((bx[B]-gx[G])*(bx[B]-gx[G])+(by[B]-gy[G])*(by[B]-gy[G]))>k)
	return false;
	for (i=1;i<=n;i++)
	if (i!=B)
	if (Gx(bx[B],by[B],gx[G],gy[G],bx[i],by[i]))	return false;
	for (i=1;i<=n;i++)
	if (i!=G)
	if (Gx(bx[B],by[B],gx[G],gy[G],gx[i],gy[i]))	return false;
	return true;
}

inline void Find(){
	int i=0,j=0,W=0,q=0;
	for (i=1;i<=n;i++)	if (strcmp(bn[i],x)==0)	{W=i;	break;}
	if (W){
		for (i=1;i<=n;i++)	if (strcmp(gn[i],y)==0)	{q=i;	break;}
	}	else {
		for (i=1;i<=n;i++)	if (strcmp(gn[i],x)==0)	{q=i;	break;}
		for (i=1;i<=n;i++)	if (strcmp(bn[i],y)==0)	{W=i;	break;}
	}
	if (Check(W,q))	w[W][q]=p;
	return;
}

inline bool dfs(int P){
	int i=0,t=0;
	vx[P]=1;
	for (i=1;i<=n;i++){
		if (vy[i]||!w[P][i])	continue;
		t=lx[P]+ly[i]-w[P][i];
		if (t==0)	{
			vy[i]=1;
			if (l[i]==-1||dfs(l[i]))	{l[i]=P;	return true;}
		}	else if (s[i]>t)	s[i]=t;
	}
	return false;
}

inline int KM(){
	int i=0,j=0,X=0,d=0,ans=0;
	memset(l,-1,sizeof(l));	memset(ly,0,sizeof(ly));
	for (X=1;X<=n;X++)
		while (1){
			memset(s,0x3f3f3f3f,sizeof(s));
			memset(vx,0,sizeof(vx));	memset(vy,0,sizeof(vy));
			if (dfs(X))	break;
			d=0x3f3f3f3f;
			for (i=1;i<=n;i++)	if (!vy[i]&&d>s[i])	d=s[i];
			for (i=1;i<=n;i++)	if (vx[i])	lx[i]-=d;
			for (i=1;i<=n;i++)	if (vy[i])	ly[i]+=d;	else s[i]-=d;
		}
	for (i=1;i<=n;i++)	if (l[i]!=-1)	ans+=w[l[i]][i];
	return ans;
}

int main(){
	freopen("cupid.in","r",stdin);
	freopen("cupid.out","w",stdout);
	scanf("%d%d",&k,&n);
	for (i=1;i<=n;i++)	scanf("%d %d %s",&bx[i],&by[i],&bn[i]);
	for (i=1;i<=n;i++)	scanf("%d %d %s",&gx[i],&gy[i],&gn[i]);
	Change_Char();
	while (1){
		scanf("%s ",&x);
		if (strlen(x)==3&&x[0]=='E'&&x[1]=='n'&&x[2]=='d')	break;
		scanf("%s %d",&y,&p);
		Change();	Find();
	}
	p=1;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++){
		if (w[i][j]!=0)	continue;	if (Check(i,j))	w[i][j]=1;
	}
	for (i=1;i<=n;i++)	lx[i]=-99999999;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
		lx[i]=max(lx[i],w[i][j]);
	printf("%d\n",KM());
	return 0;
}