torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder, Single Round Match 667, Division 2, Level 1 : PointDistance

問題概要

 平面上の 2 点 $A$, $B$ が与えられる.以下の条件を満たす点 $C$ を 1 つ求めよ.

  • $C \neq A$ かつ $C \neq B$
  • $C$ のそれぞれの座標は $-100$ 以上 $100$ 以下の整数
  • 2 点間の距離を $d$ として,$d( A, C ) > d( B, C )$

 なお,$A$, $B$ の各座標の絶対値は $50$ 以下であり,$A \neq B$ である.

解法

 $A$, $B$ より,$C$ の方が座標幅に関する制約が緩いので,絶対値が大きな座標値を使うことで $A$, $B$ に重なってしまうことを防ぐことができます.具合的には,$( 100, 100 )$, $( 100, -100 )$, $( -100, 100 )$, $( -100, -100 )$ のどれかに $C$ を置くとよい感じになります.これらから適切な点を選ぶことで,距離に関する条件も満たすことができます.
 選ぶべき点は,それぞれの座標軸を独立に考えて,$B$ に近い方の点です.例えば $X$ 軸について考えると,$A_x \leq B_x$ なら $C_x = 100$ として,そうでなければ $C_x = -100$ とします.

コード

class PointDistance
{
public:
	vector <int> findPoint( int x1, int y1, int x2, int y2 )
	{
		const int dx = x2 - x1, dy = y2 - y1;
		return { sign( dx ) * 100, sign( dy ) * 100 };
	}

	int sign( const int d )
	{
		return 0 <= d ? 1 : -1;
	}
};