www.cnblogs.com/shaokele/
AtCoder Grand Contest 025 Problem D##
Time Limit: 2 Sec
Memory Limit: 1024 MBDescription###
Takahashi is doing a research on sets of points in a plane. Takahashi thinks a set (S) of points in a coordinate plane is a good set when (S) satisfies both of the following conditions:
• The distance between any two points in (S) is not (sqrt{D1}).
• The distance between any two points in (S) is not (sqrt{D2}) .
Here, (D1) and (D2) are positive integer constants that Takahashi specified.
Let (X) be a set of points ((i,j)) on a coordinate plane where (i) and (j) are integers and satisfy (0≤i,j<2N).
Takahashi has proved that, for any choice of (D1) and (D2), there exists a way to choose (N^2) points from (X) so that the chosen points form a good set. However, he does not know the specific way to choose such points to form a good set. Find a subset of (X) whose size is (N^2) that forms a good set.
Input###
• (1≤N≤300)
• (1≤D1≤2×105)
• (1≤D2≤2×105)
• All values in the input are integers.
Input is given from Standard Input in the following format:
(N) (D_1) (D_2)
Output###
Print N2 distinct points that satisfy the condition in the following format:
(x_1 y_1)
(x_2 y_2)
:
(x_{N^2} y_{N^2})
Here, (xi,yi) represents the i-th chosen point. (0≤xi,yi<2N) must hold, and they must be integers. The chosen points may be printed in any order. In case there are multiple possible solutions, you can output any.
Sample Input 1###
2 1 2
Sample Output 1###
0 0
0 2
2 0
2 2
Sample Input 2###
3 1 5
Sample Output 2###
0 0
0 2
0 4
1 1
1 3
1 5
2 0
2 2
2 4
题目地址： AtCoder Grand Contest 025 Problem D
题目大意：
输⼊ (n, d_1, d_2)，
你要找到 (n^2) 个整点 (x, y) 满⾜ (0 ≤ x, y < 2n)。 并且找到的任意两个点距离，既不是 (sqrt{d1}，也不是 sqrt{d2})。
题解：
这是个分析题⽬。 **
简单来说，所有距离为 (sqrt{d_1}) 的点连边，可以得到⼀个⼆分图。(d_2) 同理。 **
这样可以把所有 (4n^2) 个点四分，⼀定有⼀块满⾜条件。 **
如果 d mod 2 = 1，如果 (a^2 + b^2 = d)，a 和 b ⼀定⼀奇⼀偶，按国际象棋⿊⽩染⾊即可。 **
如果 d mod 4 = 2，如果 (a^2 + b^2 = d)，a 和 b ⼀定都是奇数，⼀⾏⿊⾊，⼀⾏⽩⾊即可。 **
如果 d mod 4 = 0，把 2 × 2 的区域看成⼀个⼤格⼦，如此类推，对 d/4 进⾏如上考虑即可。**
AC代码
#include <cstdio>
using namespace std;
int n,d1,d2,s;
int f[620][620];
void work(int d){
int p=0;
while(d%4==0){
d/=4;
p++;
}
if(d&1){
for(int i=0;i<2*n;i++)
for (int j=0;j<2*n;j++)
if(((i>>p)+(j>>p))&1)
f[i][j]=1;
}else{
for(int i=0;i<2*n;i++)
for(int j=0;j<2*n;j++)
if((i>>p)&1)
f[i][j]=1;
}
}
int main(){
scanf("%d%d%d",&n,&d1,&d2);
work(d1);
work(d2);
for(int i=0;i<2*n;i++){
for(int j=0;j<2*n;j++){
if(s<n*n && !f[i][j]){
printf("%d %d
",i,j);
s++;
}
}
}
return 0;
}