bzoj3621我想那还真是令人高兴啊

bzoj3621我想那还真是令人高兴啊

bzoj3621我想那还真是令人高兴啊

题意:

T组数据,每组给出两个三角形各点坐标,要求求出一个点使第一个三角形可以绕这个点放缩和旋转得到另一个三角形。T≤10,坐标为≤10000的实数,数据保证三角形不用平移,答案保留三位小数。

题解:

复数既是一种数,又可以当做一种独特的二维向量,因为其数的特点可以用来解方程,又因为其向量的特点可以表示二维的点和变换。两个复数的积在几何上定义为把它转化为向量后极角相加,长度相乘,正可以用来表示放缩和旋转变换。因此设A,B,C为变换前三角形三个顶点(用复数表示),T为变换复数,P为绕的那个点,A',B',C'表示变换后的点。于是可以列方程(A-P)*T=(A'-P) (B-P)*T=(B'-P) (C-P)*T=(C'-P),我们可以枚举A,B,C分别是第一个三角形的哪个顶点,然后联立前两道解出T代入第三道验证。然而本傻逼忘记枚举了导致WA了好几发,顺便安利STL的complex类,已经包装好了复数的常用运算。

代码:

 #include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <complex>
#define inc(i,j,k) for(int i=j;i<=k;i++)
using namespace std; complex <double> a,b,c,d,e,f,t,p,g;
int T;
int main(){
scanf("%d",&T); while(T--){
double x,y;
scanf("%lf%lf",&x,&y); a.real(x); a.imag(y);
scanf("%lf%lf",&x,&y); b.real(x); b.imag(y);
scanf("%lf%lf",&x,&y); c.real(x); c.imag(y);
scanf("%lf%lf",&x,&y); d.real(x); d.imag(y);
scanf("%lf%lf",&x,&y); e.real(x); e.imag(y);
scanf("%lf%lf",&x,&y); f.real(x); f.imag(y);
g.real(1.000000),g.imag(0.000000); t=(e-d)/(b-a); p=(a*t-d)/(t-g);
if(abs(((c-p)*t-(f-p)).real())<1e-&&abs(((c-p)*t-(f-p)).imag())<1e-){
printf("%.6lf %.6lf\n",p.real(),p.imag()); continue;
}
swap(b,c); t=(e-d)/(b-a); p=(a*t-d)/(t-g);
if(abs(((c-p)*t-(f-p)).real())<1e-&&abs(((c-p)*t-(f-p)).imag())<1e-){
printf("%.6lf %.6lf\n",p.real(),p.imag()); continue;
}
swap(a,b); t=(e-d)/(b-a); p=(a*t-d)/(t-g);
if(abs(((c-p)*t-(f-p)).real())<1e-&&abs(((c-p)*t-(f-p)).imag())<1e-){
printf("%.6lf %.6lf\n",p.real(),p.imag()); continue;
}
swap(b,c); t=(e-d)/(b-a); p=(a*t-d)/(t-g);
if(abs(((c-p)*t-(f-p)).real())<1e-&&abs(((c-p)*t-(f-p)).imag())<1e-){
printf("%.6lf %.6lf\n",p.real(),p.imag()); continue;
}
swap(a,b); t=(e-d)/(b-a); p=(a*t-d)/(t-g);
if(abs(((c-p)*t-(f-p)).real())<1e-&&abs(((c-p)*t-(f-p)).imag())<1e-){
printf("%.6lf %.6lf\n",p.real(),p.imag()); continue;
}
swap(b,c); t=(e-d)/(b-a); p=(a*t-d)/(t-g);
if(abs(((c-p)*t-(f-p)).real())<1e-&&abs(((c-p)*t-(f-p)).imag())<1e-){
printf("%.6lf %.6lf\n",p.real(),p.imag()); continue;
}
}
return ;
}

20160609

05-20 02:23