首页 > 代码库 > HDU 4998 Rotate

HDU 4998 Rotate

2024-07-22 11:19:32   223人阅读

Rotate

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 210    Accepted Submission(s): 110


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


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

题目大意 :某个平面绕每个点逆时针旋转一个弧度值，将该过程等效为该平面绕着一个点逆时针旋转一个弧度值，求出等效点的坐标和旋转弧度值。

题目分析 :任意取两个点通过一组旋转得到另外两个对应的点，再求对应直线的垂直平分线交于一点，该点就是所要求的点的坐标，弧度考虑可以用反三角函数求出，这里需要注意一个问题，比赛时wa到死，就是旋转的方向问题，这里可以用向量的差乘来处理

代码 :
#include <cstdio>
#include <cstring>
#include <cmath>
#define PI 4.0 * atan(1.0)
using namespace std;
struct Move
{   
    double x, y, p;
}move[15];
int n;

double Dist(double x1, double y1, double x2, double y2)  //求两点间距离
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

double calx(double x, double y)  //求逆时针旋转后的x坐标
{
    double x1, y1;
    for(int i = 0; i < n; i++)
    {
        x1 = (x - move[i].x) * cos(move[i].p) - (y - move[i].y) * sin(move[i].p) + move[i].x;
        y1 = (x - move[i].x) * sin(move[i].p) + (y - move[i].y) * cos(move[i].p) + move[i].y;
        x = x1;
        y = y1;
    }
    return x1;
}

double caly(double x, double y)  //求逆时针旋转后的y坐标
{
    double x1, y1;
    for(int i = 0; i < n; i++)
    {
        x1 = (x - move[i].x) * cos(move[i].p) - (y - move[i].y) * sin(move[i].p) + move[i].x;
        y1 = (x - move[i].x) * sin(move[i].p) + (y - move[i].y) * cos(move[i].p) + move[i].y;
        x = x1;
        y = y1;
    }
    return y1;
}

int main()
{
    int ca;
    scanf("%d", &ca);
    while(ca--)
    {
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
            scanf("%lf %lf %lf", &move[i].x, &move[i].y, &move[i].p);
        //任意取两个点
        double x1 = 34.11111111;
        double y1 = 1.4211111111;
        double x3 = 42.3111111111;
        double y3 = 2.32111111111;
        //求出这两个点逆时针旋转后的两个点
        double x2 = calx(x1, y1);
        double y2 = caly(x1, y1);
        double x4 = calx(x3, y3);
        double y4 = caly(x3, y3);
        //通过y = kx + b;联立解得两垂直平分线的交点
        double x = ((y1 + y2 - y3 - y4) * (y1 - y2) * (y3 - y4) + (x4 * x4 - x3 * x3) * (y1 - y2) - (x2 * x2 - x1 * x1) * (y3 - y4))
        / (2 * (x4 - x3) * (y1 - y2) - 2 * (x2 - x1) * (y3 - y4));
        double y = (((x2 - x1) / (y1 - y2)) * (x - (x1 + x2) / 2) + (y1 + y2) / 2);
        //圆的半径
        double r = Dist(x, y, x1, y1);
        //某两个对应点的距离
        double dist = Dist(x1, y1, x2, y2);
        //通过三角函数关系求出弧度
        double angel = 2 * asin(dist / (2 * r));
        //通过向量叉乘确定方向
        double d1 = (x1 - x) * (y2 - y) - (x2 - x) * (y1 - y);
        //方向判定
        if(d1 < 0)
            angel = 2 * PI - angel; 
        //精度特判
        if(fabs(x) < 1e-10)
            x = 0;
        if(fabs(y) < 1e-10)
            y = 0;
        printf("%.10f %.10f %.10f\n", x, y, angel);
    }
}


HDU 4998 Rotate


联系
我们