#P9716. 碰壁

    ID: 6342 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2700省选/NOI-反射展开法事件驱动模拟扩展 CRT扩展欧几里得算法事件排序二分查找普通并查集奇偶性分析

碰壁

题目描述

平面上有一个 nn 行 mm 列的矩形网格,左下角坐标为 (0,0)(0,0),右上角坐标为 (m,n)(m,n)。nn 与 mm 互质,且 mm 为奇数。

一个大小可忽略的小球从 (m/2,0)(m/2,0) 出发,初速度为 (−1/2,1/2)(-1/2,1/2),即向左上方运动。某些格子各放有一个方块,方块占据整个格子。小球碰到网格外边界或方块边界时发生镜面反射。每次小球撞到方块后,被撞到的方块立即消失。

已知所有方块的位置,求从小球出发到所有方块消失所需的时间。

输入格式

第一行三个整数 m,n,km,n,k,依次表示列数、行数和方块数。

接下来 kk 行,每行两个整数 x,yx,y,表示一个方块的右上角坐标为 (x,y)(x,y)。保证 (x,y)≠((m+1)/2,1)(x,y)\ne((m+1)/2,1)。

输出格式

输出一行一个整数,表示所有方块消失的时间。

样例

5 4 3
1 1
1 2
1 4
42

数据范围

  • 对于 20% 的数据,1≤n,m,k≤3001\le n,m,k\le300。
  • 对于 70% 的数据,1≤n,m,k≤30001\le n,m,k\le3000。
  • 对于全部数据,1≤n,m,k≤1061\le n,m,k\le10^6,k≤mn−1k\le mn-1,所有输入均为整数。原题共 10 个测试点,每个占 10%。

原题时间限制 1 秒,内存限制 512 MB。

原 PDF 题面