记录编号	97028	评测结果	AAAAAAAAAA
题目名称	[CTSC 2000] 丘比特的烦恼	最终得分	100
用户昵称	◆半城烟沙灬為你打天下	是否通过	通过
代码语言	Pascal	运行时间	0.000 s
提交时间	2014-04-16 15:22:24	内存使用	0.00 MiB

Type
    sky=record
    na:string;
    xx,yy:extended;
end;
Var
   x,y,father:array[0..105]of longint;
   vx,vy:array[0..105]of boolean;
   w:array[0..105,0..105]of longint;
   p:array[0..200]of sky;
   n,m,i,j,k,a,b,c,ans:longint;
   d:extended;
   ss,s:string;
function max(x,y:extended):extended;
begin
     if x<y then exit(y) else exit(x);
end;
function min(x,y:extended):extended;
begin
     if x>y then exit(y) else exit(x);
end;
function dfs(k:longint):boolean;
var
   i,j:longint;
begin
     if k=0 then exit(false);
     vx[k]:=true;
     for i:=1 to n do
      begin
       if (vy[i]=false) and (x[k]+y[i]=w[k,i]) then
        begin
         vy[i]:=true;
         if (father[i]=0) or (dfs(father[i])) then
          begin
           father[i]:=k;
           exit(true);
          end;
        end;
      end;
     exit(false);
end;
Begin
assign(input,'cupid.in');
assign(output,'cupid.out');
reset(input);
rewrite(output);
     readln(d);
     readln(n);
     for i:=1 to 2*n do
      begin
       readln(s);
       j:=1;
       while (s[j+1]<>' ') do inc(j);
       val(copy(s,1,j),p[i].xx,a);
       j:=j+2;
       k:=1;
       while (s[j+k]<>' ') do inc(k);
       val(copy(s,j,k),p[i].yy,a);
       p[i].na:=copy(s,j+k+1,length(s)-j-k);
       for j:=1 to length(p[i].na) do p[i].na[j]:=upcase(p[i].na[j]);
      end;
     readln(s);
     for i:=1 to n do
      for j:=1 to n do
       w[i,j]:=1;
     while s<>'End' do
      begin
       i:=1;k:=1;
       while s[i+k]<>' ' do inc(k);
       ss:=copy(s,i,k);
       for j:=1 to length(ss) do ss[j]:=upcase(ss[j]);
       for a:=1 to 2*n do
        if ss=p[a].na then break;
       i:=i+k+1;
       k:=1;
       while s[i+k]<>' ' do inc(k);
       ss:=copy(s,i,k);
       for j:=1 to length(ss) do ss[j]:=upcase(ss[j]);
       for b:=1 to 2*n do
        if ss=p[b].na then break;
       val(copy(s,i+k+1,length(s)-i-k),c,j);
       if a>b then w[b,a-n]:=c
       else w[a,b-n]:=c;
       readln(s);
      end;
//--------------------------------------------------------------------------//
     for i:=1 to n do
      for j:=1 to n do
       begin
        if sqr(p[i].xx-p[j+n].xx)+sqr(p[i].yy-p[j+n].yy)>sqr(d) then
         begin
          w[i,j]:=-100000000;
          continue;
         end;
        for k:=1 to 2*n do
         if (k<>i) and (k<>j+n) and ((p[i].xx-p[j+n].xx)*(p[i].yy-p[k].yy)=
         (p[i].yy-p[j+n].yy)*(p[i].xx-p[k].xx)) then
          begin
           if (p[k].xx>max(p[i].xx,p[j+n].xx)) or
              (p[k].xx<min(p[i].xx,p[j+n].xx)) or
              (p[k].yy>max(p[i].yy,p[j+n].yy)) or
              (p[k].yy<min(p[i].yy,p[j+n].yy)) then continue;
           w[i,j]:=-100000000;
           break;
          end;
        end;
//--------------------------------------------------------------------------//
      fillchar(y,sizeof(y),0);
      fillchar(x,sizeof(x),0);
      for i:=1 to n do
       for j:=1 to n do
        x[i]:=trunc(max(x[i],w[i,j]));
      fillchar(father,sizeof(father),0);
      for k:=1 to n do
       repeat
        fillchar(vx,sizeof(vx),false);
        fillchar(vy,sizeof(vy),false);
        if dfs(k) then break;
        c:=10000000;
        for i:=1 to n do
         begin
          if not vx[i] then continue;
          for j:=1 to n do
           begin
            if vy[j] then continue;
            c:=trunc(min(c,x[i]+y[j]-w[i,j]));
           end;
         end;
        for i:=1 to n do
         begin
          if vx[i] then x[i]:=x[i]-c;
          if vy[i] then y[i]:=y[i]+c;
         end;
        until false;
//-------------------------------------------------------------------------//
       ans:=0;
       for i:=1 to n do ans:=ans+w[father[i],i];
       writeln(ans);
close(input);
close(output);
end.