CF35C.Fire Again

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

After a terrifying forest fire in Berland a forest rebirth program was carried out. Due to it NN rows with MM trees each were planted and the rows were so neat that one could map it on a system of coordinates so that the jj -th tree in the ii -th row would have the coordinates of (i,j)(i,j) . However a terrible thing happened and the young forest caught fire. Now we must find the coordinates of the tree that will catch fire last to plan evacuation.

The burning began in KK points simultaneously, which means that initially KK trees started to burn. Every minute the fire gets from the burning trees to the ones that aren’t burning and that the distance from them to the nearest burning tree equals to 1.

Find the tree that will be the last to start burning. If there are several such trees, output any.

输入格式

The first input line contains two integers N,MN,M ( 1<=N,M<=20001<=N,M<=2000 ) — the size of the forest. The trees were planted in all points of the ( x,yx,y ) ( 1<=x<=N,1<=y<=M1<=x<=N,1<=y<=M ) type, xx and yy are integers.

The second line contains an integer KK ( 1<=K<=101<=K<=10 ) — amount of trees, burning in the beginning.

The third line contains KK pairs of integers: x1,y1,x2,y2,...,xk,ykx_{1},y_{1},x_{2},y_{2},...,x_{k},y_{k} ( 1<=xi<=N,1<=yi<=M1<=x_{i}<=N,1<=y_{i}<=M ) — coordinates of the points from which the fire started. It is guaranteed that no two points coincide.

输出格式

Output a line with two space-separated integers xx and yy — coordinates of the tree that will be the last one to start burning. If there are several such trees, output any.

输入输出样例

  • 输入#1

    3 3
    1
    2 2
    

    输出#1

    1 1
    
  • 输入#2

    3 3
    1
    1 1
    

    输出#2

    3 3
    
  • 输入#3

    3 3
    2
    1 1 3 3
    

    输出#3

    2 2
首页