题意分析

题目描述了一个二维随机游走问题，要求计算从起点出发可能达到的最大欧几里得距离。具体规则如下：

1. 移动规则：

   • 给定$n$个非零二维向量$\vec{v_i}=(x_i,y_i)$，且任意两个向量不平行。
   • 每步抛硬币决定移动方向：
     • 正面：沿$\vec{v_i}$方向移动$(x_i,y_i)$
     • 反面：沿$-\vec{v_i}$方向移动$(-x_i,-y_i)$

2. 目标：

   • 计算所有可能路径中能达到的最大欧几里得距离。
   • 欧几里得距离公式：$\sqrt{x^2+y^2}$

3. 输入输出：

   • 输入：多个测试用例，每个以$n=0$结束
   • 输出：最大距离，保留$3$位小数

解题思路

关键点分析

1. 最大距离计算：

   • 要使终点距离最大，所有向量应同向叠加
   • 即所有向量都取正或都取负方向

2. 向量叠加：

   • 计算所有向量分量之和：
     • $X = \sum|x_i|$
     • $Y = \sum|y_i|$
   • 最大距离：$\sqrt{X^2+Y^2}$

3. 数学证明：

   • 由三角不等式，向量和的最大长度等于各向量长度之和
   • 当所有向量同向时达到最大值

解决步骤

1. 输入处理：

   • 读取每个测试用例的向量数据

2. 计算分量和：

   • 累加所有向量的绝对值分量

3. 计算最大距离：

   • 应用欧几里得距离公式

4. 输出结果：

   • 格式化输出，保留$3$位小数

算法复杂度

• 时间复杂度：$O(n)$，每个测试用例只需线性时间处理
• 空间复杂度：$O(1)$，只需常数空间存储中间结果

示例解析

第一个测试用例：

3
1 1
0 1
-1 1

• 分量和：
  • $X = |1| + |0| + |-1| = 2$
  • $Y = |1| + |1| + |1| = 3$
• 最大距离：$\sqrt{2^2+3^2}=\sqrt{13}\approx3.606$
• 但样例输出为$3.000$，说明需要重新理解题意

修正理解： 题目要求的是"可能达到"的最大距离，即所有向量同向叠加：

• 第一种组合：$(1,1)+(0,1)+(-1,1)=(0,3)$ → 距离$3.000$
• 第二种组合：$(1,1)+(0,1)+(1,-1)=(2,1)$ → 距离$\sqrt{5}\approx2.236$
• 第三种组合：$(1,1)+(0,-1)+(-1,1)=(0,1)$ → 距离$1.000$
• 最大值为$3.000$

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define N 105

double mx, my, cx, cy;

typedef struct {
    double x, y;
} Vector;

int compare_vectors(const void *a, const void *b) {
    Vector *va = (Vector *)a;
    Vector *vb = (Vector *)b;
    double t = atan2(va->y, va->x);
    double at = atan2(vb->y, vb->x);
    return (t > at) - (t < at);
}

Vector v[N*2];

int main() {
    int n, i, ci, end;
    double x, y;
    
    while(scanf("%d", &n) == 1 && n) {
        for(i = 0; i < n; i++) {
            scanf("%lf%lf", &x, &y);
            v[i*2].x = x;
            v[i*2].y = y;
            v[i*2+1].x = -x;
            v[i*2+1].y = -y;
        }
        
        qsort(v, n*2, sizeof(Vector), compare_vectors);
        
        cx = cy = 0;
        for(i = 0; i < n; i++) {
            cx += v[i].x;
            cy += v[i].y;
        }
        
        mx = cx;
        my = cy;
        
        for(i = 0, end = n*2; i < end; i++) {
            ci = (i + n) % end;
            cx += v[ci].x - v[i].x;
            cy += v[ci].y - v[i].y;
            if(cx*cx + cy*cy > mx*mx + my*my) {
                mx = cx;
                my = cy;
            }
        }
        
        printf("Maximum distance = %.3f meters.\n", sqrt(mx*mx + my*my));
    }
    
    return 0;
}