【题意】
有一个r*c的方格,青蛙会以相同的向量v=(x,y)跳过,跳过的地方留下痕迹,青蛙在格子外哪里出发都有可能,问有最多有多少只青蛙。
【输入】
r c
n
以下n行每行描述一个点。
【输出】
最多有多少只青蛙。
比较暴力……
program poj1054; type point=record x,y:longint; end; var n,r,c,i,j,k,ans,x,y:longint; v:array [0..5001,0..5001] of boolean; p:array [0..5001] of point; function max (a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; procedure swap (var a,b:point); var i:point; begin i:=a; a:=b; b:=i; end; procedure qsort (s,e:longint); var i,j:longint; k:point; begin if s>=e then exit; i:=s; j:=e; k:=p[(s+e) div 2]; while i<=j do begin while (p[i].x<k.x)or((p[i].x=k.x)and(p[i].y<k.y)) do inc(i); while (p[j].x>k.x)or((p[j].x=k.x)and(p[j].y>k.y)) do dec(j); if i>j then break; swap(p[i],p[j]); inc(i); dec(j); end; qsort(s,j); qsort(i,e); end; function dfs (x,y,xx,yy:longint):longint; var k:longint; begin k:=2; while (x+xx>0)and(x+xx<=r)and(y+yy>0)and(y+yy<=c) do if v[x+xx,y+yy] then begin inc(k); x:=x+xx; y:=y+yy; end else exit(0); exit(k); end; begin read(r,c); read(n); fillchar(v,sizeof(v),false); for i:=1 to n do begin read(p[i].x,p[i].y); v[p[i].x,p[i].y]:=true; end; qsort(1,n); ans:=2; for i:=1 to n-1 do for j:=i+1 to n do begin x:=p[j].x-p[i].x; y:=p[j].y-p[i].y; if (p[i].x-x>0)and(p[i].y-y>0)and (p[i].x-x<=r)and(p[i].y-y<=c) then continue; if (p[i].x+(ans-1)*x>0)and(p[i].x+(ans-1)*x<=r) and(p[i].y+(ans-1)*y>0)and(p[i].y+(ans-1)*y<=c) then ans:=max(ans,dfs(p[j].x,p[j].y,x,y)); end; if ans=2 then writeln(0) else writeln(ans); end.