oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

HDU1590 Searching

Posted on 2007-02-17 02:40 oyjpart 阅读(1202) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC或其他比赛

题目大意是给出第一条向量和一个公比k 以及一个旋转角度A
然后沿第一条向量左旋A角度 前进k*第一条向量的距离 得到第二条向量
如此下去 最终停在一个点上
题目虽然结果只需要输出3为 但是想从精度上打主意进行近似模拟是不行的
正确的解法是吧这个坐标平面看成一个复数平面
设向量V : x + yi
则左旋A角度之后的向量应该是xcosA - ysinA + (ycosA + xsinA)i
(我是化成极坐标得出来的) 相当于乘上cosA+sinAi
而距离变成k倍实际上就是乘上k
那么无穷尽的旋转 其实就是首相为x+yi, 公比为kcosA+ksinAi的等比数列 其和为
           x+yi
————————
(1 - kcosA) - ksinAi
复数的除法可以转化成乘法(两边同时成一共轭复数即可) 这样就能够解决问题了

Solution
//by oyjpArt
#include <stdio.h>
#include <math.h>
const double EPS = 10e-6;

int main() {
 double a, b, r, x, y, A, k, c, d;
 while(scanf("%lf %lf %lf %lf", &x, &y, &A, &k) != EOF) {
  A = A * acos(-1)/180.0;
  a = 1.0 - k * cos(A);
  b = -k * sin(A);
  c = x * a + y * b;
  d = y * a - x * b;
  r = a * a + b * b;
  printf("(%.3lf,%.3lf)\n", c/r+EPS, d/r+EPS);
 }
 return 0;
}
//BTW: #include <complex> & use overloaded / could make division easier.
Like this:
#include <stdio.h>
#include <math.h>
#include <complex>
using namespace std;
typedef complex<double> Comp;
const double EPS = 10e-6;

int main() {
 double x, y, A, k;
 while(scanf("%lf %lf %lf %lf", &x, &y, &A, &k) != EOF) {
  A = A * acos(-1)/180.0;
  Comp a(x, y);
  Comp b(1-k*cos(A), -k*sin(A));
  Comp c = a/b;
  printf("(%.3lf,%.3lf)\n", c.real()+EPS, c.imag()+EPS);
 }
 return 0;
}

 


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理