Captain Marmot （枚举/dfs+逆时针旋转+判断是否是正方形）

题目链接：http://codeforces.com/contest/474/my

Captain Marmot wants to prepare a huge and important battle against his enemy, Captain Snake. For this battle he has n regiments, each consisting of 4 moles.

Initially, each mole i (1 ≤ i ≤ 4n) is placed at some position (xi, yi) in the Cartesian plane. Captain Marmot wants to move some moles to make the regiments compact, if it's possible.

Each mole i has a home placed at the position (ai, bi). Moving this mole one time means rotating his position point (xi, yi) 90 degrees counter-clockwise around it's home point (ai, bi).

A regiment is compact only if the position points of the 4 moles form a square with non-zero area.

Help Captain Marmot to find out for each regiment the minimal number of moves required to make that regiment compact, if it's possible.

Input

The first line contains one integer n (1 ≤ n ≤ 100), the number of regiments.

The next 4n lines contain 4 integers xi, yi, ai, bi ( - 104 ≤ xi, yi, ai, bi ≤ 104).

Output

Print n lines to the standard output. If the regiment i can be made compact, the i-th line should contain one integer, the minimal number of required moves. Otherwise, on the i-th line print "-1" (without quotes).

Examples

Input

Output

Note

In the first regiment we can move once the second or the third mole.

We can't make the second regiment compact.

In the third regiment, from the last 3 moles we can move once one and twice another one.

In the fourth regiment, we can move twice the first mole and once the third mole.

题意：给定T表示测试数，下面每4行是一组测试

每行2个点，a b 每次a可以绕着b逆时针转90°

问最少操作多少次使得4个a构成一个正方形。

思路：暴力枚举每一种情况，判断是否是正方形，找出最少旋转数。

知识点：

1.将（x,y）绕（rx0,ry0）逆时针旋转a弧度，得到的坐标（x0,y0）：

x0= (x - rx0)*cos(a) - (y - ry0)*sin(a) + rx0 ;
y0= (x - rx0)*sin(a) + (y - ry0)*cos(a) + ry0 ;

正方形判定定理：

有一个角是直角的菱形是正方形
一组邻边相等的矩形是正方形
对角线互相垂直的矩形是正方形
四边相等,有一个角是直角的四边形是正方形（先证菱形）
一组邻边相等且有一个角是直角的平行四边形是正方形（先证菱形）
四边均相等,对角线互相垂直平分且相等的平面四边形（先证菱形）

具体判断的时候我是这样想的：4个点两两组合有6种情况（即有6条线段）4条边，2条对角线。

对角线一定比边长，所以短的那4条一定相等，对角线也一定相等，再用勾股定理证明存在一个直角

（感觉自己的判断怪怪的，好像是验证是不是正方形）

for循环枚举实现代码https://blog.csdn.net/s_black/article/details/46999195

我是用dfs实现的

这个是用浮点型做的，浮点型不能判断直接相等，要做差判断误差，所以要注意精度，一开始精度设为1e-8wa了，改成1e-6就过了（不建议这样做，除非给的点是浮点型）（整型的做法在下面）

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-6;
struct point {
	double x,y;
} a[5],b[5];
bool equal(double a,double b) {
	if(a<b) swap(a,b);
	return a-b<eps;
}
double dis(point a,point b) {
	return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
double d[10];
bool judge() {
	d[0]=dis(a[1],a[2]);
	d[1]=dis(a[1],a[3]);
	d[2]=dis(a[1],a[4]);
	d[3]=dis(a[2],a[3]);
	d[4]=dis(a[2],a[4]);
	d[5]=dis(a[3],a[4]);
	sort(d,d+6);
	if(d[0]&&equal(d[0],d[3])&&equal(d[4],d[5])&&equal(2*d[0]*d[0],d[4]*d[4])){
		return true;
	}
		
	else
		return false;

}
int ans;
void dfs(int p,int res) {
	if(p>4) {
		if(judge()) {
			ans=min(ans,res);
		}
		return ;
	}
	point t=a[p],tmp=a[p];
	for(int i=0; i<=3; i++) {
		double x=t.x,y=t.y;
		if(i>0) {
			t.x=-1*(y-b[p].y)+b[p].x;
			t.y=(x-b[p].x)+b[p].y;
			a[p]=t;
		}
		dfs(p+1,res+i);
		a[p]=tmp;
	}
}
int main() {
	int n;
	scanf("%d",&n);
	while(n--) {
		for(int i=1; i<=4; i++) {
			scanf("%lf%lf%lf%lf",&a[i].x,&a[i].y,&b[i].x,&b[i].y);
		}
		ans=16;
		dfs(1,0);
		if(ans==16) printf("-1\n");
		else printf("%d\n",ans);
	}
	return 0;
}

这个是整型的，直接判断是否相等

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
struct point {
	int x,y;
} a[5],b[5];
ll dis(point a,point b) {
	return (ll)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
ll d[10];
bool judge() {
	d[0]=dis(a[1],a[2]);
	d[1]=dis(a[1],a[3]);
	d[2]=dis(a[1],a[4]);
	d[3]=dis(a[2],a[3]);
	d[4]=dis(a[2],a[4]);
	d[5]=dis(a[3],a[4]);
	sort(d,d+6);
	if(d[0]&&d[0]==d[3]&&d[4]==d[5]&&2*d[0]==d[4]){  
		return true;
	}
		
	else
		return false;

}
int ans;
void dfs(int p,int res) {
	if(p>4) {
		if(judge()) {
			ans=min(ans,res);
		}
		return ;
	}
	point t=a[p],tmp=a[p];
	for(int i=0; i<=3; i++) {
		int x=t.x,y=t.y;
		if(i>0) {
			t.x=-1*(y-b[p].y)+b[p].x;
			t.y=(x-b[p].x)+b[p].y;
			a[p]=t;
		}
		dfs(p+1,res+i);
		a[p]=tmp;
	}
}
int main() {
	int n;
	scanf("%d",&n);
	while(n--) {
		for(int i=1; i<=4; i++) {
			scanf("%d%d%d%d",&a[i].x,&a[i].y,&b[i].x,&b[i].y);
		}
		ans=16;
		dfs(1,0);
		if(ans==16) printf("-1\n");
		else printf("%d\n",ans);
	}
	return 0;
}