首页 > 代码库 > HDU 4998 Rotate（计算几何 绕点旋转）

HDU 4998 Rotate（计算几何 绕点旋转）

2024-07-22 11:08:12   225人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4998



Problem Description
Noting is more interesting than rotation!

Your little sister likes to rotate things. To put it easier to analyze, your sister makes n rotations. In the i-th time, she makes everything in the plane rotate counter-clockwisely around a point ai by a radian of pi.

Now she promises that the total effect of her rotations is a single rotation around a point A by radian P (this means the sum of pi is not a multiplier of 2π).

Of course, you should be able to figure out what is A and P :).
 

Input
The first line contains an integer T, denoting the number of the test cases.

For each test case, the first line contains an integer n denoting the number of the rotations. Then n lines follows, each containing 3 real numbers x, y and p, which means rotating around point (x, y) counter-clockwisely by a radian of p.

We promise that the sum of all p‘s is differed at least 0.1 from the nearest multiplier of 2π.

T<=100. 1<=n<=10. 0<=x, y<=100. 0<=p<=2π.
 

Output
For each test case, print 3 real numbers x, y, p, indicating that the overall rotation is around (x, y) counter-clockwisely by a radian of p. Note that you should print p where 0<=p<2π.

Your answer will be considered correct if and only if for x, y and p, the absolute error is no larger than 1e-5.
 

Sample Input
1
3
0 0 1
1 1 1
2 2 1
 

Sample Output
1.8088715944 0.1911284056 3.0000000000
 

Source
2014 ACM/ICPC Asia Regional Anshan Online


解析系转载：

平面上有一个二维坐标轴上,进行n次操作，把坐标轴绕着(x,y) (这个坐标总是初始坐标轴的坐标) 逆时针转p弧度。
最后的结果相当于进行一次操作，即绕着(X, Y) 逆时针旋转了P弧度。求 X,Y,P，题目保证总有解.
其实可以发现，最后的P是n次的pi的和，因为这和绕什么点旋转无关。（画一个图理解一下吧）
对任意点(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 ;
可以假设两个点a, b(两个足够了), 任意指定其坐标, 可以算出旋转后的对应点a‘, b‘, 
前面已经求出了P， 现在只要求出旋转中心A即可， 利用 dis(A, a) == dis(A, a‘) 和 dis(A, b) == dis(A, b‘) 直接列方程可以求出A的坐标！


代码如下：

#include <cstdio>
#include <cmath>
#define pi acos(-1.0)
int main()
{
    int  t;
    int n;
    double x1, y1, x2, y2, r;
    double tx1, ty1, tx2, ty2;
    double rx0, ry0, a;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        x1 = y1 = 0;
        x2 = y2 = 1;
        r = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf("%lf%lf%lf", &rx0, &ry0, &a);
            r += a;
            if(r >= 2*pi)
                r -= 2*pi;
            tx1 = (x1 - rx0) * cos(a) - (y1 - ry0) * sin(a) + rx0;
            ty1 = (x1 - rx0) * sin(a) + (y1 - ry0) * cos(a) + ry0;
            tx2 = (x2 - rx0) * cos(a) - (y2 - ry0) * sin(a) + rx0;
            ty2 = (x2 - rx0) * sin(a) + (y2 - ry0) * cos(a) + ry0;
            x1 = tx1, y1 = ty1;
            x2 = tx2, y2 = ty2;
        }
        double t1 = (x1*x1+y1*y1)*(2*y2-2)-2*y1*(x2*x2+y2*y2)+4*y1;
        double t2 = 4*y1-4*y1*x2+4*x1*y2-4*x1;
        double x = t1/t2;
        double t3 = (x1*x1+y1*y1)-2*x*x1;
        double t4 = 2*y1;
        double y = t3/t4;
        printf("%lf %lf %lf\n",x,y,r);
    }
    return 0;
}



PS:最后给出求解的方程：

我们设a的坐标为(0, 0)，b的坐标为(1, 1)；

A的坐标为(x, y)；

①：dis(A, a) == dis(A, a‘) ：(x - x1)2 + (y - y1)2 = (x - 0)2 + (y - 0)2;

②：dis(A, b) == dis(A, b‘) ：(x - x2)2 + (y - y2)2 = (x - 1)2 + (y - 1)2;

联立①②方程解出A(x, y)的坐标即可！



HDU 4998 Rotate（计算几何 绕点旋转）


联系
我们