题目分析

本题需要计算在无限时间后，IOI 热病最多能感染多少居民。关键在于分析居民在不同方向选择下是否可能相遇，从而传播疾病。

核心思路

1. 相遇条件分析

两个居民 $i$ 和 $j$ 能在某个时刻相遇，当且仅当存在方向选择使得他们的路径相交。通过坐标变换和几何分析，可以将这个问题转化为图论问题。

2. 坐标变换技巧

代码中使用了多种坐标变换：

• 旋转和缩放坐标系
• 将曼哈顿距离问题转化为更易处理的形式
• 通过不同的变换角度（0°, 90°, 180°, 270°）覆盖所有可能的方向组合

3. 图论建模

• 将居民视为图中的节点
• 如果两个居民可能相遇，则在它们之间建立有向边（表示感染可能传播）
• 使用 Dijkstra 算法计算从居民 1 出发最多能到达的节点数

主要步骤

1. 坐标预处理

   • 将所有坐标相对于居民1进行平移
   • 乘以2避免浮点数运算

2. 四种方向变换

   fo(i,0,3){
       fo(j,1,n) swap(q[j].x,q[j].y),q[j].x*=-1;
       work();
   }
   

3. 几何关系建立

   • 根据坐标和方向状态分组
   • 建立居民之间的相遇关系
   • 使用multiset维护几何约束

4. Dijkstra算法扩展

   • 从感染源居民1开始
   • 根据几何关系逐步扩展可能被感染的居民
   • 维护每个居民被感染的最早时间

关键优化

1. 坐标离散化：处理大范围坐标值
2. 扫描线技巧：高效处理几何关系
3. 多角度覆盖：通过4次旋转确保覆盖所有可能的方向组合
4. 集合维护：使用multiset动态维护和查询几何约束

复杂度分析

• 坐标变换：$O(n)$
• 排序和分组：$O(n \log n)$
• 图构建：$O(n \log n)$
• Dijkstra算法：$O(n \log n)$
• 总复杂度：$O(n \log n)$，能够处理 $n \leq 10^5$ 的数据规模

总结

本题的难点在于将几何运动问题转化为图论问题。通过巧妙的坐标变换和几何分析，结合高效的图算法，成功解决了在无限时间内疾病传播的最大范围问题。