题目描述

Bessie is trapped in a triangular maze with N rows . A three row maze is shown below:
The i'th row of the maze contains 2*i-1 triangles. Numbering from the left, the triangles are named (i,1), (i,2), and so on.
Bessie can travel to the (often three) triangles which share an edge with her current triangle. For example, if she is at (3, 3), she can travel to (3, 2), (3, 4) and (4, 4). Bessie takes one minute to travel from one triangle to the next.
FJ has learned the Bessie is trapped and knows by tracking her iPhone that she starts her exit trek at triangle (Si,Sj). FJ's love for Bessie knows no bounds so he wants her back in the minimum possible time.
The maze has M () exits found in locations throughout the set of triangles. Any one of these will enable Bessie to escape. Once she enters an exit triangle, she leaves the maze in just one more minute.
Find the minimum time in minutes, T, required for Bessie to exit the maze and report the optimal exit location she uses, (OUTi, OUTj). If more than one location requires only T minutes, output the location with the smallest row. If two optimal rows are the same, output the one with smaller column.

输入描述:

* Line 1: Two space-separated integers: N and M
* Line 2: Two space-separated integers: Si and Sj
* Lines 3..M+2: Line i+2 contains two space-separated integers that are the triangle location of exit i: Ei and Ej

输出描述:

* Line 1: Two space-separated integers: OUTi and OUTj
* Line 2: A single integer: T

示例1

输入
4 2 
2 1 
3 5 
4 4 
输出
4 4
4

解答

肯定是先将所有的出口按字典序排序,从小到大枚举终点,然后要O(1)的算出起点和终点的距离.

考虑到这些三角形很不好搞,可以把每一行复制一遍,然后把三角形的每一行都往前推一下,就像这样:

O O OO OO OOO OOO OOOO 这是n=4的情况.

可以发现,在这个新图里面,每个点都可以往上下走,奇数行的可以往右下方走,偶数行的可以往左上方走.

那么就可以贪心了.

先求出起点和终点在新图中的对应编号.

假设终点在下面.

首先先让终点一直往正上方走,知道走到和起点同行.

还可以算出走到上面的过程中最多可以往左边走多少.

那么判断一下起点和终点的列的关系.

若起点的列在终点的列的右边,那么就要一上一下的往右走.

若在左边,那么再判断一下是否可以在往上走的过程中可以走到.

若不能走到,也要一上一下的往左边走.

不知道标签为什么会有一个逆元 

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<complex>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
#include<vector>
#define maxn 10010
using namespace std;
struct data{
  int x,y;
}t[maxn],ans;
inline bool cmp(const data &A,const data &B){
  return A.x==B.x?A.y<B.y:A.x<B.x;
}
int main(){
  int n,m,sx,sy,zx=1<<30;
  scanf("%d%d%d%d",&n,&m,&sx,&sy);
  if(sy&1) sx=2*sx-1;else sx=2*sx-2;
  sy=(sy+1)/2;
  for(int i=1;i<=m;i++){
    scanf("%d%d",&t[i].x,&t[i].y);
  }
  sort(t+1,t+m+1,cmp);
  for(int i=1;i<=m;i++){
    int x1=t[i].x,x2=sx,y1=t[i].y,y2=sy,tmp;
    if(y1&1) x1=2*x1-1;else x1=2*x1-2;
    y1=(y1+1)/2;
    if(x1>x2) swap(x1,x2),swap(y1,y2);
    tmp=x2-x1;int can=(x2-x1+(bool)(x2&1))/2;
    if(y1>=y2) tmp+=(y1-y2)*2;

    else{
      y2-=can;
      if(y2>y1)tmp+=(y2-y1)*2;
    }
    if(tmp+1<zx) zx=tmp+1,ans=t[i];
  }
  printf("%d %d\n%d",ans.x,ans.y,zx);
  return 0;
}


来源：zjo_2001