首页 > 代码库 > hdu 4998

hdu 4998

2024-07-22 17:42:51   219人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4998

 

这道题，在比赛的时候看了很久，才明白题目的大意。都怪自己不好好学习英语。后来经过队友翻译才懂是什么意思。

题目大意：二维平面内的物品，把它们绕给定的n个点，逆时针旋转。 现在求通过一个A点，逆时针旋转角度P就能完成这个操作。

问：这个点A的坐标，P的角度。

解题思路：随意找个点t1,绕着n个点旋转得到t2。点A一定在线段t1t2的垂直平分线上。再找一点t3，绕n个点旋转得到t4。

线段t1t2的垂直平分线和线段t3t4的垂直平分线相交一点，这点就是A点。证明过程就不写了，可以画图看看。

旋转的角度是向量At1和向量At2的夹角Θ，或是2∏-Θ

 

  1 #include<cstdio>  2 #include<cmath>  3 #include<iostream>  4 using namespace std;  5   6 struct Point{  7     double x, y;  8   9     Point(double x = 0, double y = 0): x(x), y(y){} 10 }; 11  12 typedef Point Vector; 13  14 const double eps = 1e-10; 15  16 int dcmp(double x){ 17     if(fabs(x) < eps) 18         return 0; 19     return x < 0 ? -1 : 1; 20 } 21  22 bool operator == (Point A, Point B){ 23     return dcmp(A.x - B.x) == 0 && dcmp(A.y - B.y) == 0; 24 } 25  26 Vector operator + (Vector A, Vector B){ 27     return Vector(A.x + B.x, A.y + B.y); 28 } 29  30 Vector operator - (Vector A, Vector B){ 31     return Vector(A.x - B.x, A.y - B.y); 32 } 33  34 Vector operator * (Vector A, double p){ 35     return Vector(A.x * p, A.y * p); 36 } 37  38 Vector operator / (Vector A, double p){ 39     return Vector(A.x / p, A.y / p); 40 } 41  42 double dot(Vector A, Vector B){//点乘 43     return A.x * B.x + A.y * B.y; 44 } 45  46 double length(Vector A){//向量的模 47     return sqrt(dot(A, A)); 48 } 49  50 double angle(Vector A, Vector B){//两个向量的夹角 51     return acos(dot(A, B) / length(A) / length(B)); 52 } 53  54 Vector rotate(Vector A, double rad){//点A绕原点旋转角度为rad 55     return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad)); 56 } 57  58 Vector normal(Vector A){//向量的法向量 59     double L = length(A); 60     return Vector(-A.y / L, A.x / L); 61 } 62  63 double cross(Vector A, Vector B){//叉乘 64     return A.x * B.y - A.y * B.x; 65 } 66  67 int n; 68 Point p[11]; 69 double ra[11]; 70  71 void input(){ 72     cin>> n; 73     for(int i = 0; i < n; ++i){ 74         cin>> p[i].x>> p[i].y>> ra[i]; 75         if(dcmp(ra[i] - 2 * acos(-1.0)) == 0 || dcmp(ra[i]) == 0){ 76         //当输入的弧度为0或者2π时，都是没用的 77             ra[i] = 0; 78             n--; 79             i--; 80         } 81     } 82 } 83  84 Vector rotate_point(Vector A){//将A点绕n个点旋转 85     for(int i = 0; i < n; ++i){ 86         A = p[i] + rotate(A - p[i], ra[i]); 87     } 88     return A; 89 } 90  91 Vector mid_point(Point A, Point B){//求两点之间的中点 92     return Vector((A.x + B.x) / 2, (A.y + B.y) / 2); 93 } 94  95 Point get_line_intersection(Point P, Vector v, Point Q, Vector w){//两直线求交点，《算法入门经典训练之南》几何 96     Vector u = P - Q; 97     double t = cross(w, u) / cross(v, w); 98     return P + v * t; 99 }100 101 void solve(){102     Point t1[2], t2[2], mid[2], vec[2];103     t1[0].x = -10;104     t1[0].y = -10;105     t1[1].x = -100;106     t1[1].y = -20;107     for(int i = 0; i < 2; ++i){108         t2[i] = rotate_point(t1[i]);109         mid[i] = mid_point(t1[i], t2[i]);110         vec[i] = normal(t1[i] - t2[i]);111     }112     Point ans = get_line_intersection(mid[0], vec[0], mid[1], vec[1]);//答案点A113     double ansp = angle(t1[0] - ans, t2[0] - ans);//旋转角度P114 115     if(cross(t1[0] - ans, t2[0] - ans)  < 0){//判断是ansp 还是2π - ansp116         ansp = 2 * acos(-1.0) - ansp;117     }118 119     if(dcmp(ans.x) == 0){//加入答案是-1e-11，如果直接输出就会是-0.0000000000120         ans.x = 0;121     }122     if(dcmp(ans.y) == 0){123         ans.y = 0;124     }125 126     printf("%.10lf %.10lf %.10lf\n", ans.x, ans.y, ansp);127 }128 129 int main(){130     //freopen("data.in", "r", stdin);131     //freopen("data.out", "w", stdout);132     int t;133     cin>> t;134     while(t--){135         input();136         solve();137     }138     return 0;139 }
AC代码

 

hdu 4998


联系
我们