Skip to content

14245: 【原4245】硬核战棋II

题目

题目描述

author: MoLe 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4245

Description

MoLe在硬核战棋游戏中又遇到了新的困难。本次他面对的是硬核战棋中的逃脱模式,这个模式在一个每个格子都拥有整数x,y坐标的网格中进行。敌人共有\(n\)名,初始状态下第\(i\)名敌人位于\((x_i,y_i)\)位置。MoLe的部队可能位于地图中的任何一个位置。游戏进行时双方轮流移动自己的棋子,每个回合可以且必须将自己的棋子向周围四个方向移动一格。敌方可以为每一个棋子分别选择移动的方向。敌方的移动没有任何的限制,(这意味着移动和可以出现棋子重叠,甚至可以与MoLe的棋子重叠,注意这是合法的)而MoLe则要保证在移动后自己的棋子不能够与敌方的棋子重叠(在MoLe开始移动之前他的棋子是允许与敌方棋子重叠的)。这个游戏由MoLe首先开始移动,MoLe的胜利条件为他可以在棋盘上合法的走无穷多步(敌方是由电脑操控的,可以假定为必然会做出最优选择)。MoLe想知道在棋盘上有多少个初始位置使得自己不能赢得这场游戏。

Input Format

第一行一个整数\(n\),表示敌方的棋子总数

接下来\(n\)行,每行共\(2\)个整数,代表第\(i\)名敌人初始所处的位置。

Output Format

输出一个整数,代表棋盘上有多少个初始位置使得MoLe不能赢得这场游戏。

Sample Input 1

4
-2 -1
0 1
0 -3
2 -1

Sample Output 1

4

Sample Input 2

16
2 1
1 2
-1 1
0 1
0 0
1 1
2 -1
2 0
1 0
-1 -1
1 -1
2 2
0 -1
-1 0
0 2
-1 2

Sample Output 2

4

Limits

对于\(30 \% \)的数据,\(1 \leq N \leq 5\)

对于\(60 \% \)的数据,\(1 \leq N \leq 100\)

对于\(100 \% \)的数据,\(1 \leq N \leq 100000, -10^5 \leq x_i, y_i \leq 10^5 \)

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!