小姬小姬小姬

时间: 1ms        内存:256M

描述:

小姬最近开始研究起了曼哈顿距离,因为他厌倦了欧氏距离的学习。

我们知道,平面内 $(x_1, y_1)$ 与 $(x_2, y_2)$ 的曼哈顿距离被定义为这两点在标准坐标系上的绝对轴距之和,即 $|x_1 – x_2| + |y_1 – y_2|$。

对于小姬来讲,他可以很容易的算出给定平面内任意多个点之间的曼哈顿距离,但是千千给小姬出了一个问题:假如我有 $\frac{n(n-1)}{2}$ 个数,它们分别代表平面中 $n$ 个点之间的曼哈顿距离,你能告诉我这 $n$ 个点的位置么?

随后的几天,小姬开始困惑了,因为他想来想去也只会算当 $n=2$ 的情形,于是便去找千千诉苦,看到这样的情形,千千只好答应降低难度,只要你算出 $n=3$ 的情形便可以啦。

你能帮小姬解决这个问题么?

输入:

输入只有一行,包含三个正整数 $a, b, c\ (1\le a, b, c \le 100)$,分别代表平面中 3 个点两两之间的曼哈顿距离。(保证输入数据有解)

输出:

输出满足题意的三个点的坐标(要求 $0 \le |x|, |y| \le 10^5$),每个点的坐标占一行,可以以任意的顺序输出,若存在多解的情况,输出任意一组即可。(如果你的答案计算出的结果与真实值相差 $10^{-6}$ 以内则被认为是正确的)

示例输入:

1 1 2

示例输出:

0.000000 0.000000
1.000000 0.000000
0.000000 1.000000

提示:

参考答案(内存最优[1120]):

#include<cstdio>
#include<cmath>
using namespace std;
int a,b,c;
int main()
{
    scanf("%d%d%d",&a,&b,&c);
    printf("0 0\n");
    printf("0 %d\n",a);
    for(int i=400;i>=-400;i--)
        for(int j=-400;j<=400;j++)
        {
            if(abs(i)+abs(j)==2*b&&abs(i)+abs(j-2*a)==2*c)
            {
                printf("%d.%d %d.%d\n",i/2,i%2?5:0,j/2,j%2?5:0);
                return 0;
            }
        }
}

参考答案(时间最优[3]):

#include <bits/stdc++.h>
#define IO                       \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
#define mem(a, x) memset(a, x, sizeof(a))
#define per(x, a, b) for (int x = a; x <= b; x++)
#define rep(x, a, b) for (int x = a; x >= b; x--)

using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const double eps = 1e-8;

int main() {
#ifdef LOCAL_IM0QIANQIAN
    freopen("test.in", "r", stdin);
//    freopen("test.out", "w", stdout);
#else
    // IO;
#endif // LOCAL_IM0QIANQIAN

    double a[3];
    cin >> a[0] >> a[1] >> a[2];
    sort(a, a + 3);
    double x = (a[1] + a[2] - a[0]) / 2.0;
    double a1 = a[1] - x;
    // double a2 = a[2] - x;
    printf("%.6f %.6f\n", 0.0, 0.0);
    printf("%.6f %.6f\n", a[0], 0.0);
    printf("%.6f %.6f\n", a1, x);
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。