[解方程]Map 2022杭电多校第6场 1009

Problem Description

Sakuyalove has a large world map MM and a small world map mm. Both of the them are in the shape of rectangle. The small map mm is compressed from the large map MM. If the length of MM is aa and the width of MM is bb, then the length of mm is kaka and the width of mm is kbkb, where 0 < k < 10exactly one point PP represents the same place in small map and large map (For example, in the following pictures, the location of the pin on both maps represents Tokyo, Japan). Sakuyalove wants to find out this point PP. Please help her.

Input

The first line contains one integer T(1\le T\le 10^5)T(1≤T≤105), described the number of test cases.

Each test case contains eight lines. Each line has two integers x, y (-10^{3}\leq x, y\leq 10 ^ 3)x,y(−103≤x,y≤103) separated by one space.

The first four lines are the coordinates of the upper left corner, the upper right corner, the lower right corner and the lower left corner of MM.

The last four lines are the coordinates of the upper left corner, the upper right corner, the lower right corner and the lower left corner of mm.

It is guaranteed that mm is within MM, both of the them are in the shape of rectangle, and mm is compressed from MM.

Please note that the upper left corner, the upper right corner, the lower right corner and the lower left corner of mm and MM are one-to-one corresponding. For example, in the picture of Hint below, the correspondence of points is A-aA−a, B-bB−b, C-cC−c, D-dD−d. But A-cA−c, B-dB−d, C-aC−a, D-bD−b is not allowed.

Output

Your output should contains TT lines. Each line contains two real numbers x, yx,y separated by one space, represents the coordinates of the point PP. Your absolute error should not exceed 10 ^ {-6}10−6.

Sample Input

1

0 5

15 5

15 0

0 0

3 2

9 5

10 3

4 0

Sample Output

6.000000 2.000000

Hint

In the first example, the picture is like this:

题意： 每组数据给出八个点，分别是一个大矩形四顶点和一个小矩形四顶点，保证小矩形一定在大矩形内部，求出点P满足P点在小矩形中的相对位置和大矩形中的相对位置相同。

分析： 设向量OP = 向量OA + lambda*向量AB + mu*向量AD，那么还应该有向量OP = 向量Oa + lambda*向量ab + mu*向量ad，二者联立消去OP得：

根据x坐标和y坐标方程解出该lambda和mu就可以求出P点坐标了，不过这题要注意精度，前期运算可以用整数进行，到了不得已的时候再转成浮点运算。 

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define double long double
using namespace std;
const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxp = 1010;
//`Compares a double to zero`
int sgn(double x)
{
	if(fabs(x) < eps)return 0;
	if(x < 0)return -1;
	else return 1;
}
//square of a double
inline double sqr(double x){return x*x;}
struct Point
{
	int x, y;
	Point(){}
	Point(int _x,int _y){x = _x, y = _y;}
	void input(){scanf("%d%d",&x,&y);}
	void output(){printf("%.2f %.2f\n",x,y);}
	bool operator == (Point b)const{return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;}
	//第一关键字为x，第二关键字为y 
	bool operator < (Point b)const{return sgn(x-b.x)== 0?sgn(y-b.y)<0:x
	Point operator -(const Point &b)const{return Point(x-b.x,y-b.y);}
	//叉积
	double operator ^(const Point &b)const{return x*b.y - y*b.x;}
	//点积
	double operator *(const Point &b)const{return x*b.x + y*b.y;}
	//返回长度
	double len(){return hypot(x,y);/*库函数*/}
	//返回长度的平方
	double len2(){return x*x + y*y;}
	//返回两点的距离
	double distance(Point p){return hypot(x-p.x,y-p.y);}
	Point operator +(const Point &b)const{return Point(x+b.x,y+b.y);}
	Point operator *(const double &k)const{return Point(x*k,y*k);}
	Point operator /(const double &k)const{return Point(x/k,y/k);}
	//`计算pa  和  pb 的夹角`
	//`就是求这个点看a,b 所成的夹角`
	//`测试 LightOJ1203`
	double rad(Point a,Point b)
	{
		Point p = *this;
		return fabs(atan2( fabs((a-p)^(b-p)),(a-p)*(b-p) ));
	}
	//`化为长度为r的向量`
	Point trunc(double r)
	{
		double l = len();
		if(!sgn(l))return *this;
		r /= l;
		return Point(x*r,y*r);
	}
	//`逆时针旋转90度`
	Point rotleft(){return Point(-y,x);}
	//`顺时针旋转90度`
	Point rotright(){return Point(y,-x);}
	//`绕着p点逆时针旋转angle`
	Point rotate(Point p,double angle)
	{
		Point v = (*this) - p;
		double c = cos(angle), s = sin(angle);
		return Point(p.x + v.x*c - v.y*s,p.y + v.x*s + v.y*c);
	}
}; 
 
Point p1[4], p2[4];
 
signed main(){
	int T;
	cin >> T;
	while(T--){
		for(int i = 0; i < 4; i++)
			p1[i].input();
		for(int i = 0; i < 4; i++)
			p2[i].input();
		Point AB = p1[1]-p1[0];
		Point ab = p2[1]-p2[0];
		Point AD = p1[3]-p1[0];
		Point ad = p2[3]-p2[0];
		Point OA = p1[0]; 
		Point Oa = p2[0];
		//x坐标方程各系数 
		int a1 = (AB-ab).x;
		int b1 = (AD-ad).x;
		int c1 = (Oa-OA).x;
		//y坐标方程各系数 
		int a2 = (AB-ab).y;
		int b2 = (AD-ad).y;
		int c2 = (Oa-OA).y;
		double mu = 1.0*(1ll*c1*a2-1ll*a1*c2)/(1ll*b1*a2-1ll*a1*b2);
		double lambda = 1.0*(c1-1ll*b1*mu)/a1;
		double x = Oa.x+ab.x*lambda+ad.x*mu;
		double y = Oa.y+ab.y*lambda+ad.y*mu;
		cout << fixed << setprecision(10) << x << " " << y << endl;
	}
	return 0;
}