torus711 のアレ

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

Codeforces #271, C : Captain Marmot

問題概要

 直交座標をもつ平面上の点が 4n 個与えられ、i 番目の点の座標は ( x_i, y_i ) である。また、i 番目の点は座標 ( a_i, b_i ) を中心に、反時計回りに \frac{ \pi }{ 2 } [rad] 回転することができる。4 つずつの塊について(すなわち、有効な k に関して添字 [ 4k, 4( k + 1 ) ) をもつ点たちについて)、点が 0 でない面積をもつ正方形をなすようにするために必要な回転の回数を求めよ。不可能な場合は -1 で示せ。

解法

 4 つずつの塊について、実際に回転回数の組み合わせを全て試しつつ判定を行うことで問題を解くことができます。回転後の点集合は、座標軸に平行でない正方形を成すことも許容される点に注意して判定しなければなりません。
 移動後の点について、異なる点同士を結んだ 6 本の線分を考えます。この線分の長さの比が 1:1:1:1:2:2 になっていれば、点集合は正方形です。この条件を満たすことと、対角線の長さが等しく、直行していることは同値であることからこの判定は妥当であると言えます。

コード

using LL = long long; using ULL = unsigned long long;
template < typename T = int > using VT = vector<T>;
template < typename T = int > using LIM = numeric_limits<T>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) (c).begin(), (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )

#define fst first
#define snd second

constexpr int INF = LIM<>::max();

#include <complex>
typedef complex<double> Point;
const double EPS = 1e-8;
const double PI = acos( -1 );

// 内積(ドット積)
double dot( const Point &a, const Point &b )
{
	return a.real() * b.real() + a.imag() * b.imag();
}

pair< LL, LL > rotate( const pair< LL, LL > &p, const pair< LL, LL > &c )
{
	pair< LL, LL > cp = MP( p.fst - c.fst, p.snd - c.snd );
	// xcos - ysin
	// xsin + ycos
	// cos := 0, sin := 1

	const LL dx = -cp.snd;
	const LL dy = cp.fst;

	return MP( c.fst + dx, c.snd + dy );
}

LL sqdist( const pair< LL, LL > &p, const pair< LL, LL > &q )
{
	const LL d1 = p.fst - q.fst, d2 = p.snd - q.snd;
	return d1 * d1 + d2 * d2;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	REP( iteration, 0, n )
	{
		VT< pair< LL, LL > > ps( 4 ), qs( 4 );
		REP( i, 0, 4 )
		{
			cin >> ps[i].fst >> ps[i].snd >> qs[i].fst >> qs[i].snd;
		}

		int res = INF;
		REP( i, 0, 4 )
		{
			REP( j, 0, 4 )
			{
				REP( k, 0, 4 )
				{
					REP( l, 0, 4 )
					{
						VT< LL > dists;
						REP( a, 0, 4 )
						{
							REP( b, 0, a )
							{
								dists.PB( sqdist( ps[a], ps[b] ) );
							}
						}
						sort( ALL( dists ) );
						
						bool ok = true;
						const LL d0 = dists[0];
						FOR( d, dists )
						{
							if ( d0 && !( d % d0 ) )
							{
								d /= d0;
							}
							else
							{
								ok = false;
							}
						}

						if ( ok && dists == VT< LL >( { 1, 1, 1, 1, 2, 2 } ) )
						{
							res = min( res, i + j + k + l );
						}

						ps[3] = rotate( ps[3], qs[3] );
					}

					ps[2] = rotate( ps[2], qs[2] );
				}

				ps[1] = rotate( ps[1], qs[1] );

			}

			ps[0] = rotate( ps[0], qs[0] );
		}

		cout << ( res == INF ? -1 : res ) << endl;
	}

	return 0;
}