题解说明

问题描述：
给定平面上 $n$ 个点和 $m$ 条无向边。要求为每个点分配一个非负半径 $r[i]$，使得对每条边 $(u,v)$，满足：

其中 $\text{dist}(u,v)$ 是两点的欧氏距离。若存在解则输出 "DA" 并给出所有半径，否则输出 "NE"。

核心思路：
$1.$ 半径表示：

• 将每个半径表示为 $r[u] = a[u].val \pm val$，其中 $val$ 是全局基准值。
• 点的类型决定是加 $val$ 还是减 $val$。

$2.$ DFS 传播约束：

• 从任意点出发，设类型 $=1$，$val=0$。
• 沿边传播：相邻点类型翻转，偏移值更新为边长减去当前点的偏移。
• 若遇到已访问点，检查一致性：
  • 类型相同：得到关于 $val$ 的方程，唯一确定 $val$。
  • 类型不同：检查 $a[u].val + a[v].val$ 是否等于边长。

$3.$ 基准值确定：

• 若分量内出现类型相同的闭合约束，则 $val$ 唯一确定。
• 否则 $val$ 未确定，但非负约束给出区间 $[L,R]$：
  • 类型 $1$：$val \geq -a[u].val$
  • 类型 $0$：$val \leq a[u].val$
• 若 $L > R$，无解。
• 在 $[L,R]$ 内选择最优 $val$，使半径平方和最小。

$4.$ 半径计算与验证：

• 根据 $val$ 计算每个点的半径。
• 若出现 $r[u] < 0$，则无解。

算法流程：
$1.$ 输入 $n,m$ 和点坐标。
$2.$ 建图，边权为两点距离。
$3.$ 对每个连通分量：

• DFS 传播约束。
• 若矛盾则输出 "NE"。
• 若无矛盾，确定 $val$ 并计算半径。
  $4.$ 若所有分量可行，输出 "DA" 和所有半径。

复杂度分析：

• 建图与 DFS：$O(n+m)$
• 每条边访问常数次
• 总复杂度 $O(n+m)$，空间 $O(n+m)$

实现细节：

• 使用 $long\ double$ 提高精度。
• $EPS = 10^{-8}$ 判断浮点相等。
• 半径非负性检查时允许微小误差。
• 多个连通分量独立处理。

总结：
该算法通过“DFS 传播约束 $+$ 基准值确定 $+$ 区间裁剪”的方式，将几何约束转化为线性方程组问题。若存在解则输出一组半径，否则输出 "NE"。

#include <stdio.h>
#include <algorithm>  // 用于min、max等函数
#include <stdlib.h>   // 用于exit函数
#include <math.h>     // 实际编译时可能需要，原代码用了编译器内置函数

// 定义长双精度浮点数，用于高精度计算
typedef long double llf;

// 宏定义：无穷大（用于初始化范围）
#define INF __builtin_inf()
// 宏定义：浮点数精度阈值，用于判断两个浮点数是否相等
#define EPS 1e-8l
// 宏定义：计算两点(i,j)之间的欧氏距离
#define dis(i,j) __builtin_sqrtl((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))
// 宏定义：判断两个浮点数是否相等（差值小于精度阈值）
#define equal(x,y) (__builtin_fabsl((x)-(y))<=EPS)

// 边的结构体（用于邻接表存储图）
struct edge {
    int v;          // 边的另一端顶点
    llf w;          // 边的权重（两点间距离）
    int nextn;      // 下一条边的索引（邻接表链式存储）
};

// 全局变量：边数组、边数量、邻接表表头
edge b[200005];    // 存储所有边，最多200004条
int bn = 0;        // 边的计数（从1开始）
int lastn[100005]; // 邻接表表头，lastn[u]表示u的第一条边索引

// 用于存储约束关系的结构体
struct value {
    int type;       // 类型（0或1，用于区分两种约束方式）
    llf val;        // 约束中的系数值
    // 构造函数
    value(): type(0), val(0.0) {}
    value(const int _type, const llf _val): type(_type), val(_val) {}
};

// 全局变量：问题参数
int n, m;              // n：顶点数；m：边数
int u, v;              // 临时变量，存储边的两个顶点
llf x[100005], y[100005]; // 存储每个顶点的坐标(x[i], y[i])
value a[100005];       // 存储每个顶点的约束信息（type和val）
int vis[100005];       // 标记顶点是否已访问（DFS用）
int st[100005], sz;    // 栈：存储当前连通分量的所有顶点，sz是栈大小
llf val;               // 全局变量：当前连通分量的基准值（用于计算半径）
int known;             // 标记是否已确定基准值val
llf r[100005];         // 存储每个顶点的半径结果

// 向邻接表添加边
// u, v：边的两个顶点；w：边的权重（两点距离）
void addEdge(const int u, const int v, const llf w) {
    b[++bn] = edge{v, w, lastn[u]};  // 新建边，指向u的上一条边
    lastn[u] = bn;                   // 更新u的表头为新边索引
}

// DFS遍历：传播约束并检查一致性
// u：当前遍历的顶点
void dfs(const int u) {
    int v;                  // 临时变量，存储邻接顶点
    st[++sz] = u;           // 将当前顶点加入连通分量栈
    vis[u] = 1;             // 标记为已访问

    // 遍历u的所有邻接边
    for (int i = lastn[u]; i > 0; i = b[i].nextn) {
        v = b[i].v;         // 邻接顶点v
        if (!vis[v]) {      // 如果v未访问，传播约束
            // v的类型与u相反（0<->1），值为边权重 - u的值
            a[v] = value(a[u].type ^ 1, b[i].w - a[u].val);
            dfs(v);         // 递归访问v
        } else {            // 如果v已访问，检查约束是否矛盾
            if (a[u].type == a[v].type) {
                // 类型相同：推导基准值val的方程，解为x
                const llf x = (a[u].type 
                    ? (b[i].w - a[u].val - a[v].val) 
                    : (a[u].val + a[v].val - b[i].w)) / 2.0;

                // 如果已有基准值且与当前解矛盾，输出"NE"并退出
                if (known && !equal(val, x)) {
                    printf("NE\n");
                    exit(0);
                }
                val = x;    // 记录基准值
                known = 1;  // 标记已确定基准值
            } else {
                // 类型不同：检查u和v的值之和是否等于边权重
                if (!equal(b[i].w, a[u].val + a[v].val)) {
                    printf("NE\n");
                    exit(0);
                }
            }
        }
    }
}

int main() {
    // 读入顶点数n和边数m
    scanf("%d%d", &n, &m);

    // 读入n个顶点的坐标（转换为长双精度）
    for (int i = 1; i <= n; i++) {
        double xx, yy;
        scanf("%lf%lf", &xx, &yy);
        x[i] = xx;
        y[i] = yy;
    }

    // 读入m条边，计算两点距离并添加到邻接表（双向边）
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        const llf d = dis(u, v);  // 计算u和v的距离
        addEdge(u, v, d);         // 添加u->v的边
        addEdge(v, u, d);         // 添加v->u的边（无向图）
    }

    // 处理每个未访问的顶点（每个连通分量）
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            // 初始化当前连通分量：以i为起点，类型1，值0
            a[i] = value(1, 0.0);
            sz = 0;         // 清空连通分量栈
            known = 0;      // 初始未确定基准值
            dfs(i);         // DFS遍历整个连通分量

            // 如果未确定基准值，计算可行范围并选择合适值
            if (!known) {
                llf L = 0.0;    // 基准值的下界
                llf R = INF;    // 基准值的上界
                llf q = 0.0, l = 0.0, c = 0.0;  // 用于计算最优基准值的系数

                // 遍历连通分量的所有顶点，更新范围和系数
                for (int j = 1; j <= sz; j++) {
                    const int u = st[j];  // 当前顶点
                    if (a[u].type) {
                        // 类型1：半径r[u] = a[u].val + val，需非负 -> val >= -a[u].val
                        L = std::max(L, -a[u].val);
                        q += 1.0;
                        l += 2.0 * a[u].val;
                        c += a[u].val * a[u].val;
                    } else {
                        // 类型0：半径r[u] = a[u].val - val，需非负 -> val <= a[u].val
                        R = std::min(R, a[u].val);
                        q += 1.0;
                        l += -2.0 * a[u].val;
                        c += a[u].val * a[u].val;
                    }
                }

                // 如果下界大于上界，无解
                if (L > R + EPS) {
                    printf("NE\n");
                    exit(0);
                }

                // 计算最优基准值（使半径平方和最小），并确保在[L, R]范围内
                val = -l / (2.0 * q);
                if (val < L) val = L;
                if (val > R) val = R;
            }

            // 计算当前连通分量所有顶点的半径，并检查是否非负
            for (int j = 1; j <= sz; j++) {
                const int u = st[j];
                // 根据类型计算半径：类型1为a[u].val + val，类型0为a[u].val - val
                r[u] = a[u].type ? (a[u].val + val) : (a[u].val - val);
                // 半径不能为负（小于-EPS视为无效）
                if (r[u] < -EPS) {
                    printf("NE\n");
                    exit(0);
                }
            }
        }
    }

    // 所有连通分量均有效，输出结果
    printf("DA\n");
    for (int i = 1; i <= n; i++) {
        printf("%lf\n", (double)r[i]);  // 输出每个顶点的半径
    }

    return 0;
}