Chinaunix

标题: 来个看似简单的数学问题，闲的来试试 [打印本页]
作者: Susake_    时间: 2014-07-22 09:57
标题: 来个看似简单的数学问题，闲的来试试
计算x和y的值:wink: (不得只是简单的使用枚举哇)
    (r1 * r1) / [(x - x1) * (x - x1) + (y - y1) * (y - y1)]
  = (r2 * r2) / [(x - x2) * (x - x2) + (y - y2) * (y - y2)]
  = (r3 * r3) / [(x - x3) * (x - x3) + (y - y3) * (y - y3)]
以上除了x，y其他都已知
输入
0 0 10
60 0 10
30 30 10
输出
30.00000 0.00000
作者: zmy235    时间: 2014-07-22 10:55
本帖最后由 zmy235 于 2014-07-22 10:56 编辑

建一个平面直角坐标系（x-xi）^2+（y-yi）^2就是点点之间距离
作者: Susake_    时间: 2014-07-22 12:28
回复 2# zmy235
你试试嘛~说的和做的可能不是一回事哇？


   
作者: fender0107401    时间: 2014-07-22 14:20
看了这个题之后，我表示十分震惊！
作者: Susake_    时间: 2014-07-22 14:55
好像记得是用近似xx解决的
不可以枚举，假设数据10^5 * 精度 10 ^ 6 = 10^ 11，以10^10每秒算，需要10秒
作者: Susake_    时间: 2014-07-22 14:56
fender0107401 发表于 2014-07-22 14:20
看了这个题之后，我表示十分震惊！

嗯？.....................
作者: fender0107401    时间: 2014-07-23 09:02
Susake_ 发表于 2014-07-22 14:56
嗯？.....................


这个题不是看似简单，其实就是很简单。。。
作者: Susake_    时间: 2014-07-23 09:45
fender0107401 发表于 2014-07-23 09:02
这个题不是看似简单，其实就是很简单。。。

能讲讲思路？  我来实现~谢谢！
作者: fender0107401    时间: 2014-07-23 11:35
Susake_ 发表于 2014-07-23 09:45
能讲讲思路？  我来实现~谢谢！


自己想想就会了，没啥复杂的。
作者: Susake_    时间: 2014-07-23 12:28
我猜你想的是化简？那样想可算不出来呀~
作者: fender0107401    时间: 2014-07-23 12:54
回复 10# Susake_

你猜错了。。。
   
作者: ssfjhh    时间: 2014-07-23 12:57
少年，不要犯懒，拿出纸和笔，用高中学的东西计算个公式出来。然后再编写程序。
没难度的事儿，只是比较烦。
作者: ssfjhh    时间: 2014-07-23 12:59
两圆求交点，再代入另外一个式子里验证哪组xy是正解或者没有解。
作者: Susake_    时间: 2014-07-23 13:24
本帖最后由 Susake_ 于 2014-07-23 21:46 编辑

不是的，不是求交点再代入，原型是这样的rt
假设有3个圆型区域，我想找出某点的到这3区域的视角相等，分析后即只需要r1/d1 = r2/d2 = r3/d3
呃....

QQ图片20140723131526.jpg (29.05 KB, 下载次数: 28)

QQ图片20140723131526.jpg
作者: Susake_    时间: 2014-07-23 13:33
算了，是这样的，取重心然后逐渐逼近最优解~
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <cstring>
  6. #include <stack>
  7. #include <map>
  8. #include <string>
  9. using namespace std;

  11. struct pt {
  12.     double x;
  13.     double y;
  14.     double r;
  15. };

  17. pt mkp(double x, double y) {
  18.     pt ret;
  19.     ret.x = x;
  20.     ret.y = y;
  21.     return ret;
  22. }

  24. double dis(pt a, pt b) {
  25.     return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  26. }

  28. double cost(pt *p, double x, double y) {
  29.     double ang[3];
  30.     for (int i = 0; i < 3; i++) ang[i] = dis(p[i], mkp(x, y)) / p[i].r;

  32.     double diff[3];
  33.     for (int i = 0; i < 3; i++) diff[i] = ang[i] - ang[(i+1)%3];

  35.     double ret = 0;
  36.     for (int i = 0; i < 3; i++) ret += diff[i] * diff[i];

  38.     return ret;
  39. }

  41. const int dx[] = {0, 1, -1, 0};
  42. const int dy[] = {1, 0, 0, -1};
  43. const double err = 1e-6;

  45. int main(int argc, char *argv[]) {
  46.     pt p[3];
  47.     for (int i = 0; i < 3; i++) scanf("%lf %lf %lf", &(p[i].x), &(p[i].y), &(p[i].r));

  49.     pt ans;
  50.     ans.x = (p[0].x + p[1].x + p[2].x) / 3.0;
  51.     ans.y = (p[0].y + p[1].y + p[2].y) / 3.0;
  52.     double ncost = cost(p, ans.x, ans.y);

  54.     pt tmp;
  55.     double step = 1.0;
  56.     bool flag = false;
  57.     for (int i = 0; i < 300000 && ncost > err; i++) {
  58.         flag = false;
  59.         for (int k = 0; k < 4; k++) {
  60.             tmp.x = ans.x + step * ((double)dx[k]);
  61.             tmp.y = ans.y + step * ((double)dy[k]);

  63.             if (ncost > cost(p, tmp.x, tmp.y)) {
  64.                 ncost = cost(p, tmp.x, tmp.y);
  65.                 ans = tmp;
  66.                 flag = true;
  67.             }
  68.         }
  69.         if (!flag) step *= 0.5;
  70.     }

  72.     if (cost(p, ans.x, ans.y) <= err)
  73.         printf("%.5lf %.5lf\n", ans.x, ans.y);
  74.     return 0;
  75. }
复制代码
作者: fender0107401    时间: 2014-07-23 13:36
少年，貌似从头到尾都只有你一个人在说“化简”什么的。。。
作者: Susake_    时间: 2014-07-23 13:44
...额...不该说“化简”的....斑竹想的啥方法啊？
作者: Susake_    时间: 2014-07-23 13:44
我只是感觉这个太麻烦了:wink:
作者: bruceteen    时间: 2014-07-23 13:58
Susake_ 发表于 2014-07-23 13:24
再一次说明化简是不可能的


为什么不可能呀？
任意两个圆的等率膨胀交点组成一个椭圆（直接化简公式，得出的也是 a*(x-b)^2 + c*(y-d)^2 = e ）
现在的问题就变成了求两个椭圆的交点。（直接方程组求解，得出的也是一个一元四次方程）

难点在于，这个公式有点长，我是没耐心和时间一步步演算下去。
作者: Susake_    时间: 2014-07-23 14:21
bruceteen 发表于 2014-07-23 13:58
为什么不可能呀？
任意两个圆的等率膨胀交点组成一个椭圆（直接化简公式，得出的也是 a*(x-b)^2 + c*( ...

嗯
过几天，试试看~
作者: Susake_    时间: 2014-07-23 14:25
本帖最后由 Susake_ 于 2014-07-23 14:30 编辑

啊啊，一元四次方程，这还要弄上高精度，pow(10^5, 4)
作者: fender0107401    时间: 2014-07-23 14:44
lz原来知道怎么算啊。。。
作者: fender0107401    时间: 2014-07-23 14:45
lz为什么不早点给出14楼那个图呢？
作者: Susake_    时间: 2014-07-23 14:52
回复 23# fender0107401

嗯
   
作者: fender0107401    时间: 2014-07-23 15:13
Susake_ 发表于 2014-07-23 14:52
回复 23# fender0107401

嗯


我觉得你好阴险啊，明明很简单，非搞的神秘兮兮的，明明有实际背景，非只给一个等式。
作者: Susake_    时间: 2014-07-23 15:15
开始真的没想到哇~~
作者: Susake_    时间: 2014-07-23 15:16
我也是后面看到有人说交点才发的不是吗？
作者: amarant    时间: 2014-07-23 16:27
fender0107401同学说了半天简单，就是没说怎么回事。看起来很利害的样子
作者: fender0107401    时间: 2014-07-23 16:36
因为。。。实在。。。太简单。。。
作者: __BlueGuy_    时间: 2014-07-23 17:41
提示: 作者被禁止或删除 内容自动屏蔽
作者: fender0107401    时间: 2014-07-23 18:59
回复 30# __BlueGuy_

三，你又出来找存在感了。

记住，要不能停啊。

还有就是，我猜你不会做！
作者: amarant    时间: 2014-07-23 19:08
同样是码农，同样拿着几毛钱的工资，谁也别看不起谁
作者: ptrees    时间: 2014-07-24 13:28
[(x - x1) * (x - x1) + (y - y1) * (y - y1)] = (r1 * r1) /k
  [(x - x2) * (x - x2) + (y - y2) * (y - y2)] = (r2 * r2) /k
[(x - x3) * (x - x3) + (y - y3) * (y - y3)]  = (r3 * r3) /k

化简一下就是2元一次方程,然后...主要懒得算了
作者: Susake_    时间: 2014-07-24 14:22
本帖最后由 Susake_ 于 2014-07-24 14:33 编辑

突然想到一句话，钱不是问题，关键是没钱！！:开个玩笑
作者: Susake_    时间: 2014-07-24 14:23
标题就说了，看似简单的数学问题！
作者: bskay    时间: 2014-07-25 12:22
做需求和 把解决方案当作需求来做,难度还是不一样的
作者: folklore    时间: 2014-07-27 21:09
楼主太坑了， 就是求三个大圆的交点的问题。
（将圆等比例放大直到相交， 用数学方法可以算出比率，所以一次性就能得出结果）。
作者: Susake_    时间: 2014-07-29 13:02
本帖最后由 Susake_ 于 2014-07-29 13:06 编辑

嗯........................
作者: Susake_    时间: 2014-07-29 13:09
等比例放大，是不是相等于r变？这好像还是原先的那种枚举呀...!r += 0.000001？
作者: w_anthony    时间: 2014-07-29 14:13
本帖最后由 w_anthony 于 2014-07-29 14:23 编辑

仔细想了一下，这题没有用到一元四次那么复杂，一元二次就够。
可以设(x-x1)是X，只要能算出X，那么x就是X+x1，这也是一样的，关键可以消掉一个麻烦的东西；反正(x-x2)和(x-x3)都是线性关系，可以化为(X-A)和(X-B)，其中A=x2-x1，B=x3-x1，同理(y-y1)也可以以同样的方式转换Y，然后r1*r1转换为R1，既然三个部分的值相等，那么其值设为Z，转换后就是：
1:X^2+Y^2=R1*Z
2:(X-A)^2+(Y-C)^2=R2*Z
3:(X-B)^2+(Y-D)^2=R3*Z
将2式展开，可以得到X^2-2AX+A^2+Y^2-2CY+C^2=R2*Z，可以发现其中有X^2+Y^2，把1式带入整理可得
4:2AX+2CY+(R2-R1)*Z-A^2-C^2=0
同理将3式展开把1式代入整理，可得
5:2BX+2DY+(R3-R1)*Z-B^2-D^2=0
联系1、4、5式，可以发现这是一个三元的方程组，次数最高是2次。而且4和5式都是一次的线性关系，这样很容易通过两边同乘以某个系数再相减的方式，得到Y关于X的关系式（乘以某个系数使4、5式的Z相等，相减约去Z）和Z关于X的关系，设它们是：
6:U1*Y=V1*X+T1
7:U2*Z=V2*X+T2
让1式两边同乘以(U1^2*U2)，这样将6和7式代入，可以得到关于X的一元二次方程组，只要解出X，那么根据6式就可以到Y。
最后由x=X+x1和y=Y+y1得到最终的x和y，完成。
具体的编码过程就完全是体力活了，没什么好说的。




欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2