2022杭电多校六 1009-Map （巴那赫不动点）

题目链接：杭电多校6 - Virtual Judge

题目：

样例输入：

1
0 5
15 5
15 0
0 0
3 2
9 5
10 3
4 0

样例输出：

6.000000 2.000000

题意：多组数据，每组数据给出两个矩形，求两个矩形的不动点坐标，也就是说求一个点使得这个点相对于这两个矩形的位置是相同的。

分析：由于矩形相邻的两条边是垂直的，所以我们可以用其相邻的两条边作为基向量，那么就会有

OP=OA+t1*AB+t2*AD

OP=OA+t3*ab+t4*ad

由于P点相对于两个矩形的位置是相同的，也就有t1=t3，t2=t4

这是一个方程两个未知量，我们可以分别对其x和y坐标分别列一个方程，这样就是两个方程两个未知量，那么直接解方程得到t1和t2然后代入方程即可求得P点坐标。

需要注意的一点是这道题目卡精度，前面最好是用int来存，最后涉及到除法时再转化为double。

下面是代码：
 

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<iomanip>
using namespace std;
int main()
{
	int T;
	cin>>T;
	int xa,xb,xc,xd,xA,xB,xC,xD;
	int ya,yb,yc,yd,yA,yB,yC,yD;
	while(T--)
	{
		scanf("%d%d%d%d%d%d%d%d",&xA,&yA,&xB,&yB,&xC,&yC,&xD,&yD);
		scanf("%d%d%d%d%d%d%d%d",&xa,&ya,&xb,&yb,&xc,&yc,&xd,&yd);
		int k11=(xB-xA)-(xb-xa);
		int k12=(xD-xA)-(xd-xa);
		int k21=(yB-yA)-(yb-ya);
		int k22=(yD-yA)-(yd-ya);
		int b1=xa-xA;
		int b2=ya-yA;
		double t1,t2;
		if(k11&&k21)
		{
			b1*=k21;k12*=k21;
			k22*=k11;b2*=k11;
			k21*=k11;k11=k21;
			t2=1.0*(b2-b1)/(k22-k12);
			t1=1.0*(b1-t2*k12)/k11;
		}
		else
		{
			if(!k11)
			{
				t2=1.0*b1/k12;
				t1=(b2-t2*k22)/k21;
			} 
			else
			{
				t2=1.0*b2/k22;
				t1=(b1-t2*k12)/k11;
			}
		}
		double x=xA+t1*(xB-xA)+t2*(xD-xA);
		double y=yA+t1*(yB-yA)+t2*(yD-yA);
		printf("%.10lf %.10lf\n",x,y);
	}
	return 0;
}