CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

[[http://poj.org/problem?id=3034|POJ 3034]]

<code cpp>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int n,d,m,f[11][40][40];
bool mp[11][40][40];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int main()
{
	while(~scanf("%d%d%d",&n,&d,&m))
	{
		if(!n&&!d&&!m)break;
		int ans=0;
		memset(mp,0,sizeof(mp));
		memset(f,0,sizeof(f));
		int maxt=0;
		for(int i=1;i<=m;i++)
		{
			int x,y,t;
			x=read(),y=read(),t=read();
			mp[t][x+6][y+6]=1;
			maxt=max(maxt,t);
		}
		for(int i=1;i<=maxt;i++)
		{
			for(int x0=-6;x0<n+6;x0++)
			{
				for(int y0=-6;y0<n+6;y0++)
				{
					for(int x1=-6;x1<n+6;x1++)
					{
						for(int y1=-6;y1<n+6;y1++)
						{
							if((x1-x0)*(x1-x0)+(y1-y0)*(y1-y0)>d*d)continue;
							int res=f[i-1][x0+6][y0+6];
							if(x1==x0&&y1==y0)res+=mp[i][x0+6][y0+6];
							else
							{
								int g=gcd(abs(x1-x0),abs(y1-y0));
								int x=x0,y=y0;
								int stx=(x1-x0)/g,sty=(y1-y0)/g;
								while(x!=x1||y!=y1)
								{
									if(mp[i][x+6][y+6])res++;
									x+=stx,y+=sty;
								}
								if(mp[i][x+6][y+6])res++;
							}
							f[i][x1+6][y1+6]=max(res,f[i][x1+6][y1+6]);
							ans=max(ans,f[i][x1+6][y1+6]);
						}
					}
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}
</code>

CVBB ACM Team

用户工具

站点工具

页面工具