問題概要
平面上の点が 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] ) ]; }