[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;

			}

		}

	}

}

巴特西

[AGC025D]Choosing Points

[AGC025D]Choosing Points

题目大意：

思路：

源代码：

最新文章

热门文章