G - Best ACMer Solves the Hardest Problem
Gym - 101955G
由于k都是整数，而在圆上的整数点很少，所以想到，tx^2 + ty^2 = K^2 ，
处理出来 K 对应的所有的 tx 和 ty，那么对于（x，y），k，圆上所有的点为 (txdirx + x, tydiry + y) , dir表示方向，每一对 tx 和 ty 对应四个点; 由于tx或者 ty==0 或者 tx == ty 导致四个点有重复，所以需要去重（sort+unique或者set、map）；答案用LL 存，
这道题细节还是比较多
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e7+5;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
#define ls (i<<1)
#define rs (i<<1|1)
#define fi first
#define se second
#define mk make_pair
#define mem(a,b) memset(a,b,sizeof(a))
LL read()
{
LL x=0,t=1;
char ch;
while(!isdigit(ch=getchar())) if(ch=='-') t=-1;
while(isdigit(ch)){ x=10*x+ch-'0'; ch=getchar(); }
return x*t;
}
LL c[6005][6005];
int xx[]={1,1,-1,-1};
int yy[]={1,-1,-1,1};
vector<pair<int,int> > a[N],cls;
inline void init()
{
for(int i=0;i<cls.size();i++)
{
int x=cls[i].fi,y=cls[i].se;
c[x][y]=0;
}
cls.clear();
}
int main()
{
for(int i=0;i<=6000;i++)//勾股定理，预处理所有的tx 和 ty,即能通过k知道x方向能有多少种移动方式、y能有多少种移动方式
{
for(int j=0;j<=6000;j++)
if(i*i+j*j<=N-5) a[i*i+j*j].push_back(mk(i,j));
else break;
}
int T=read(),test=0;
while(T--)
{
int n=read(),m=read();
for(int i=1;i<=n;i++)
{
int x=read(),y=read(),w=read();
c[x][y]=w;
cls.push_back(mk(x,y) );
}
LL lastans=0;
printf("Case #%d:
",++test);
while(m--)
{
int cmd=read(),x=read(),y=read();
x=(x+lastans)%6000+1;
y=(y+lastans)%6000+1;
if(cmd==1)
{
int w=read();
cls.push_back(mk(x,y) );
c[x][y]=w;
}
else if(cmd==2) c[x][y]=0;
else if(cmd==3)
{
set<pair<int,int> >s;//存在坐标重复，例如x、y方向移动tx、ty=0
或者tx=ty
int k=read(),w=read();
for(int i=0;i<a[k].size();i++)
{
pair<int,int> tmp=a[k][i];
for(int j=0;j<4;j++)
{
int dx=x+tmp.fi*xx[j]; // tx=tmp.fi ty=tmp.se
int dy=y+tmp.se*yy[j];
if(dx<=6000&&dx>=1&&dy>=1&&dy<=6000&&c[dx][dy]) s.insert(mk(dx,dy) );
}
}
for(set<pair<int,int> >::iterator it=s.begin();it!=s.end();it++)
{
pair<int,int> tmp=*it;
c[tmp.fi][tmp.se]+=w;
cls.push_back(mk(tmp.fi,tmp.se));
}
}
else
{
LL ans=0;
int k=read();
set<pair<int,int> > s;
for(int i=0;i<a[k].size();i++)
{
pair<int,int> tmp=a[k][i];
//printf("tx=%d ty=%d
",tmp.fi,tmp.se);
for(int j=0;j<4;j++)
{
int dx=x+tmp.fi*xx[j];
int dy=y+tmp.se*yy[j];
if(dx<=6000&&dx>=1&&dy>=1&&dy<=6000&&c[dx][dy]) s.insert(mk(dx,dy) );//printf("dx=%d dy=%d c=%d
",dx,dy,c[dx][dy]);
}
}
for(set<pair<int,int> >::iterator it=s.begin();it!=s.end();it++)
{
pair<int,int> tmp=*it;
ans+=c[tmp.fi][tmp.se];
//printf("dx=%d dy=%d c=%d
",tmp.fi,tmp.se,c[tmp.fi][tmp.se]);
}
printf("%lld
",ans);
lastans=ans;
}
}
init();
}
return 0;
}
/*
2
3 6
2999 3000 1
3001 3000 1
3000 2999 1
1 2999 3000 1
4 2999 2999 1
2 2995 2996
3 2995 2995 1 1
4 2995 2995 1
4 3000 3000 1
3 6
2999 3000 1
3001 3000 1
3000 2999 1
1 2999 3000 1
4 2999 2999 1
2 2995 2996
3 2995 2995 1 1
4 2995 2995 1
4 3000 3000 1
*/