kmjp's blog

競技プログラミング参加記です

CSAcademy Round #32 : E. Equidistant Points

Dより簡単だった。
https://csacademy.com/contest/round-32/task/equidistant-points/

問題

2次元座標上に以下を満たすようにN個の点を配置せよ。

  • 距離が1である2点の組がちょうどN個ある
  • それ以外の組は距離が1未満である。

解法

まず正三角形を作れば3個の頂点で3つの距離が1の組が作れる。
たとえば (0,0),(1.0),(1/2, \sqrt{3}/2)に3点を置いたとする。
あとは原点を中心とする扇形の弧 (\cos\theta, \sin\theta) (0^\circ \lt \theta \lt 60^\circ)に残り(N-3)個の点を配置すれば、それらは原点との距離が1で他の点との距離は1未満になる。

int N;
double X[2020],Y[2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	double pi=atan(1)*4;
	
	cin>>N;
	_P("0 0\n");
	FOR(i,N-1) {
		double deg=i*60.0/(N-2);
		deg = deg*pi/180;
		_P("%.9lf %.9lf\n",cos(deg),sin(deg));
	}
}

まとめ

constructiveだから難易度高め判定なのかな?