首页 > 代码库 > HDU 1700 Points on Cycle （几何 向量旋转）
HDU 1700 Points on Cycle （几何 向量旋转）
http://acm.hdu.edu.cn/showproblem.php?pid=1700
题目大意：
二维平面，一个圆的圆心在原点上。给定圆上的一点A，求另外两点B,C，B、C在圆上，并且三角形ABC的周长是最长的。
解题思路：
我记得小学的时候给出个一个定理，在园里面正多边形的的周长是最长的，这个定理我不会证明。
所以这里是三角形，当三角形为正三角形的时候，周长是最长的。
因为圆心在原点，所以我就向量（x，y）绕原点逆时针旋转120度和顺时针旋转120度。给定的点A可以看成（x，y）向量。
向量旋转是有公式的（算法竞赛入门经典 训练指南 P256）。
AC代码：
1 #include<cmath> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 6 const double PI = acos(-1.0); 7 8 struct Point{ 9 double x, y;10 11 Point(double x = 0, double y = 0): x(x), y(y){}12 13 void scan(){14 scanf("%lf%lf", &x, &y);15 }16 17 void print(){18 printf("%.3lf %.3lf", x, y);19 }20 21 bool operator < (const Point &other){22 return y < other.y || (y == other.y && x < other.x);23 }24 };25 26 typedef Point Vector;27 28 Vector rotate(Vector A, double rad){//向量旋转公式29 return Vector(A.x * cos(rad) - A.y * sin(rad), A.y * cos(rad) + A.x * sin(rad));30 }31 32 int main(){33 int t;34 Point p[3];35 scanf("%d", &t);36 while(t--){37 p[0].scan();38 39 p[1] = rotate(p[0], PI * 2 / 3);//逆时针旋转120度40 p[2] = rotate(p[0], -PI * 2 / 3);//顺时针旋转120度41 42 if(p[2] < p[1]) swap(p[1], p[2]);//按题目要求输出43 44 p[1].print(); putchar(‘ ‘);45 p[2].print(); putchar(‘\n‘);46 }47 return 0;48 }
HDU 1700 Points on Cycle （几何 向量旋转）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。