[AGC025D]Choosing Points

题目大意：

输⼊\(n(n\le300),d_1,d_2\)，你要找到\(n^2\)个整点\((x,y)\)满⾜\(0\le x,y<2n\)。并且找到的任意两个点距离，既不是\(\sqrt{d_1}\)，也不是\(\sqrt{d_2}\)。

思路：

所有距离为\(\sqrt{d_1}\)的点连边，可以得到一个⼆分图。\(d_2\)同理。注意到满足\(a^2+b^2=d\)的\((a,b)\)只有\(\mathcal O(n)\)个，可以得到\(\mathcal O(n^3)\)的二分图染色做法。

源代码：

#include<cmath>
#include<cstdio>
#include<cctype>
#include<vector>
inline int getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
const int N=600;
int n,d1,d2,col[2][N*N];
std::vector<std::pair<int,int>> v[2];
inline int id(const int &x,const int &y) {
    return x*N+y;
}
inline bool check(const int &x) {
    return 0<=x&&x<n*2;
}
void dfs(const int &x,const int &t) {
    const int i=x/N,j=x%N;
    for(auto &d:v[t]) {
        const int nx=i+d.first,ny=j+d.second;
        if(!check(nx)||!check(ny)) continue;
        const int y=id(i+d.first,j+d.second);
        if(!col[t][y]) {
            col[t][y]=col[t][x]==1?2:1;
            dfs(y,t);
        }
    }
}
int main() {
    n=getint(),d1=getint(),d2=getint();
    for(register int i=0;i<=d1;i++) {
        const int j=sqrt(d1-i*i);
        if(i*i+j*j!=d1) continue;
        v[0].emplace_back(std::make_pair(i,j));
        v[0].emplace_back(std::make_pair(-i,j));
        v[0].emplace_back(std::make_pair(i,-j));
        v[0].emplace_back(std::make_pair(-i,-j));
    }
    for(register int i=0;i<=d2;i++) {
        const int j=sqrt(d2-i*i);
        if(i*i+j*j!=d2) continue;
        v[1].emplace_back(std::make_pair(i,j));
        v[1].emplace_back(std::make_pair(-i,j));
        v[1].emplace_back(std::make_pair(i,-j));
        v[1].emplace_back(std::make_pair(-i,-j));
    }
    for(register int i=0;i<n*2;i++) {
        for(register int j=0;j<n*2;j++) {
            if(!col[0][id(i,j)]) {
                col[0][id(i,j)]=1;
                dfs(id(i,j),0);
            }
            if(!col[1][id(i,j)]) {
                col[1][id(i,j)]=1;
                dfs(id(i,j),1);
            }
        }
    }
    for(register int i=0,cnt=0;i<n*2;i++) {
        for(register int j=0;j<n*2;j++) {
            if(col[0][id(i,j)]==1&&col[1][id(i,j)]==1) {
                printf("%d %d\n",i,j);
                if(++cnt==n*n) return 0;
            }
        }
    }
}                

转载于:https://www.cnblogs.com/skylee03/p/9291993.html