题目大意

给定一个正 $N$ 边形，每条边和对角线都被染成三种颜色之一。需要判断：

1. 给定的对角线集合是否构成一个有效的三角剖分
2. 如果是有效的三角剖分，那么它是否是三色的（即每个三角形的三条边颜色互不相同）

问题分析

第一部分：验证三角剖分的有效性

一个有效的三角剖分必须满足以下条件：

1. 对角线数量：恰好有 $N-3$ 条对角线
2. 无交叉：任意两条对角线不能在多边形内部相交（只能在端点相交）
3. 完全三角化：所有对角线将多边形分割成 $N-2$ 个三角形
4. 无重复边：没有重复的对角线
5. 合法端点：对角线的端点必须是多边形的顶点，且不能是多边形的边

验证方法：

• 检查对角线数量是否为 $N-3$
• 使用扫描线算法或基于栈的方法检查对角线是否相交
• 验证所有三角形是否覆盖整个多边形且无重叠

第二部分：验证三色条件

对于三角剖分中的每个三角形，检查其三边颜色：

1. 获取三角形：从三角剖分中识别出所有三角形
2. 颜色检查：对于每个三角形，检查其三边是否颜色互不相同
3. 边颜色来源：
   • 多边形的边：从输入的颜色字符串获取
   • 对角线：从输入的对角线描述获取

关键点：

• 每个三角形恰好由3条边组成
• 三条边必须分别染成1、2、3三种不同颜色
• 需要建立完整的多边形图结构，包含所有边和对角线的颜色信息

算法设计

数据结构设计

struct Edge {
    int u, v, color;
    bool is_diagonal;
};

struct Triangle {
    int edges[3];  // 存储三条边的索引或颜色
};

主要步骤

1. 输入处理

   • 读取测试点类型（可忽略）
   • 读取多边形边数 $N$
   • 读取多边形边的颜色
   • 读取 $N-3$ 条对角线的信息

2. 三角剖分验证

   • 检查对角线数量
   • 构建完整的多边形图
   • 验证对角线不相交
   • 验证形成完整的三角剖分

3. 三色条件验证

   • 从三角剖分中提取所有三角形
   • 对每个三角形检查三边颜色是否互异
   • 统计验证结果

4. 输出结果

   • 无效三角剖分 → neispravna triangulacija
   • 有效三角剖分但非三色 → neispravno bojenje
   • 有效且三色 → tocno

实现细节

三角剖分验证算法

对于大规模数据（$N \leq 2 \times 10^5$），需要使用高效的验证算法：

• 基于耳剪裁（Ear Clipping）：验证给定的对角线是否构成合法的耳分解
• 单调多边形分解：将多边形分解为单调片段进行验证
• 双向链表：维护多边形的顶点连接关系

对角线相交检测

使用扫描线算法：

• 将所有边和对角线按端点坐标排序
• 使用平衡二叉树维护当前活动的线段
• 检查新加入的线段是否与活动线段相交

三角形提取

从三角剖分中提取三角形的方法：

• 遍历所有顶点，找到形成三角形的三条边
• 使用深度优先搜索遍历三角剖分的对偶图
• 确保每个三角形被恰好计数一次

复杂度分析

• 时间复杂度：$O(N \log N)$，主要来自排序和扫描线算法
• 空间复杂度：$O(N)$，存储边、顶点和临时数据结构

特殊情况处理

1. 小多边形：$N = 4$ 时只有1条对角线，1个三角形
2. 凸多边形：所有对角线都在多边形内部不相交
3. 颜色重复：注意多边形边界上的边可能颜色相同

总结

本题综合考察了：

• 计算几何中的多边形三角剖分
• 图论中的平面图性质
• 算法设计中的验证问题
• 大规模数据处理能力