首页 > 代码库 > HDU 4998 Rotate --几何
HDU 4998 Rotate --几何
题意:给n个点(x,y,p),从1~n,一次每次所有点绕着第 i 个点(原来的)逆时针转pi个弧度,问最后所有点的位置相当于绕哪个点旋转多少弧度,求出那点X和弧度P
解法:直接模拟旋转,每次计算新的坐标,最后选两个新的点分别和他们原来的点连一条线,两条线的中垂线的交点即为圆心,求出了圆心就可以求出转了多少弧度了。
注意判中垂线垂直x轴的情况以及n==1的情况。
最后角度要根据位置关系判下正负。
代码:
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#define pii acos(-1.0)#define eps 1e-8using namespace std;#define N 17typedef struct point{ double x,y,radi; int ind; point(double x=0,double y=0):x(x),y(y){}}Vector;struct Point{ double x,y; Point(double x = 0,double y = 0):x(x),y(y){ }};Vector pi[N];Point np[N];int n;int dcmp(double x){ if(fabs(x)<eps) return 0; return x < 0 ? -1:1;}Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}Vector operator - (point A,point B){return Vector(A.x-B.x,A.y-B.y);}Vector operator * (Vector A,double p){return Vector(A.x*p,A.y*p);}Vector operator / (Vector A,double p){return Vector(A.x/p,A.y/p);}bool operator == (const point& a,const point& b){return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;}bool operator < (const point& a,const point& b){return a.x<b.x ||(a.x==b.x&&a.y<b.y);} //比较和排序可用double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;} //叉积 ,大于零说明B在A的左边,小于零说明B在A的右边double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;} //点积double Length(Vector A){return sqrt(Dot(A,A));} //向量长度double Angle(Vector A,Vector B){return acos(Dot(A,B)/Length(A)/Length(B));};Vector Rotate(Vector A,double rad){return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}//rad为弧度,向量逆时针旋转radint main(){ int t,i,j; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%lf%lf%lf",&pi[i].x,&pi[i].y,&pi[i].radi),pi[i].ind = i; np[i].x = pi[i].x; np[i].y = pi[i].y; } if(n == 1) { printf("%.10f %.10f %.10f\n",pi[1].x,pi[1].y,pi[1].radi); continue; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { Vector k = Vector(np[j].x-pi[i].x,np[j].y-pi[i].y); k = Rotate(k,pi[i].radi); np[j].x = pi[i].x + k.x; np[j].y = pi[i].y + k.y; } } Point A,B,C,D; A = Point(pi[1].x,pi[1].y); B = np[1]; C = Point(pi[2].x,pi[2].y); D = np[2]; Point Mid1 = Point((A.x+B.x)/2.0,(A.y+B.y)/2.0); Point Mid2 = Point((C.x+D.x)/2.0,(C.y+D.y)/2.0); double k1,k2; double Ix,Iy; if(dcmp(A.y-B.y) == 0) { if(dcmp(D.x-C.x) == 0) k2 = 0.0; else { k2 = (D.y-C.y)/(D.x-C.x); k2 = -1.0/k2; } Ix = Mid1.x; Iy = Mid2.y + k2*(Mid1.x-Mid2.x); } else if(dcmp(D.y-C.y) == 0) { if(dcmp(B.x-A.x) == 0) k1 = 0.0; else { k1 = (B.y-A.y)/(B.x-A.x); k1 = -1.0/k1; } Ix = Mid2.x; Iy = Mid1.y + k1*(Mid2.x-Mid1.x); } else { k1 = (B.y-A.y)/(B.x-A.x); k1 = -1.0/k1; k2 = (D.y-C.y)/(D.x-C.x); k2 = -1.0/k2; double b1 = -k1*Mid1.x + Mid1.y; double b2 = -k2*Mid2.x + Mid2.y; Ix = (b2-b1)/(k1-k2); Iy = k1*Ix + b1; } Vector ka = Vector(pi[1].x-Ix,pi[1].y-Iy); Vector kb = Vector(np[1].x-Ix,np[1].y-Iy); double ang = Angle(ka,kb); double coss = Cross(ka,kb); if(dcmp(coss-0.0) == -1) ang = 2.0*pii-ang; printf("%.10f %.10f %.10f\n",Ix,Iy,ang); } return 0;}
HDU 4998 Rotate --几何
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。