首页 > ACM题库 > HDU-杭电 > HDU 3809-Decrypt coordinate[解题报告]HOJ
2015
04-13

HDU 3809-Decrypt coordinate[解题报告]HOJ

Decrypt coordinate

问题描述 :

For national security, the coordinate systems of public map service are all in an encryption system. This means that when you got the latitude and longitude coordinates from a GPS device, you cannot finger out the real place at a public map with that coordinates.
We know an encryption system, which works as:
x1 = x �C sqrt(y)
y1 = y �C sqrt(x)
Now, we got some coordinates of POIs (point of interest, http://en.wikipedia.org/wiki/Point_of_interest, which you can just think as some points)
But even we have that formulations of how to encrypt coordinates, still we cannot decrypt any POI coordinate. Can you help us to decrypt all the POI coordinates?

输入:

The first line contains a single integer T, indicating the number of test cases.
Each test case consists of two float number(x, y) in a single line.

Technical Specification

1. 1 <= T <= 10000
2. 0 <= x, y <= 10000

输出:

The first line contains a single integer T, indicating the number of test cases.
Each test case consists of two float number(x, y) in a single line.

Technical Specification

1. 1 <= T <= 10000
2. 0 <= x, y <= 10000

样例输入:

4
500.116 5000
0 0
10000 10000
5000 5000

样例输出:

Case 1: 570.995444 5023.895511
Case 2: 0.000000 0.000000
Case 3: 10100.501250 10100.501250
Case 4: 5071.212446 5071.212446

题意:

x1 = x – sqrt(y);

y1 = y – sqrt(x);

已知x1, y1, 求x, y, 其中x >= 0, y >= 0.

 

这个方程正常方法是难以解决的, 将方程转化为

x = x1 + sqrt(y);

y = y1 + sqrt(x);

可以发现x >= x1, y >= y1.

所以可以用迭代法无限逼近x, y

x = x + sqrt(y);

y = y + sqrt(x);

x, y初始化为x1, y1.

 

#include <iostream>

#include <cmath>

using namespace std;

const double eps = 1e-8;

int main()

{

    int test, cas;

    double x1, y1, tx, ty, x, y;

    cin >> test;

    for (cas = 1; cas <= test; cas++)

    {

        cin >> x1 >> y1;

        x = x1; y = y1;

        do {

            tx = x;

            ty = y;

            x = x1 + sqrt(ty);

            y = y1 + sqrt(tx);

        } while (fabs(x - tx) > eps || fabs(y - ty) > eps);

        printf("Case %d: %.6f %.6f/n", cas, x, y);

    }

    return 0;

}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/racebug2010/article/details/6423065


  1. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  2. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?