torus711 のアレ

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

TopCoder, Single Round Match 668, Division 2, Level 2 : IsItASquare

問題概要

 平面上の点が 4 個与えられる.これらの点が正方形を成すか?
 なお,与えられる点は相異なる.

解法

 正方形の性質の内,次の二つを利用します.

  • 全ての辺の長さが等しい
  • 対角線の長さが等しい

 与えられた 4 点から 2 点を選んで線分で結ぶことを考えると,点の選び方によって 6 本の線分を引くことができます.4 点が四角形を成すとすれば,この内 4 本が辺で,2 本が対角線になります.また,正方形の辺は対角線より短いので,線分の長さを昇順ソートすると,手前の 4 つが辺の長さ,残り 2 つが対角線の長さということになります.従って,手前 4 つと後ろ 2 つがそれぞれ等しければ,4 点は正方形を成すと言えます.
 定数個の点及び線分に関する処理だけなので $O( 1 )$ です.

コード

template < typename T = int > using VT = vector< T >;

#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define ALL( c ) ( c ).begin(), ( c ).end()

#define PB push_back
#define EB emplace_back

const char *MSG[] = { "Not a square", "It's a square" };

#include <complex>
using Point =  complex< double >;
constexpr double EPS = 1e-8;

// a == b
bool eq( const double a, const double b )
{
	return abs( a - b ) <= EPS;
}

class IsItASquare
{
public:
	string isSquare( vector <int> x, vector <int> y )
	{
		VT< Point > ps;
		REP( i, 4 )
		{
			ps.EB( x[i], y[i] );
		}

		VT< double > lens;
		REP( i, 4 )
		{
			REP( j, i )
			{
				lens.PB( abs( ps[i] - ps[j] ) );
			}
		}
		sort( ALL( lens ) );

		REP( i, 1, 4 )
		{
			if ( !eq( lens[0], lens[i] ) )
			{
				return MSG[0];
			}
		}
		return MSG[ eq( lens[4], lens[5] ) ];
	}