AT_arc184_d.[ARC184D] Erase Balls 2D

NOI/NOI+/CTSC

通过率:0%

AC君温馨提醒

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

题目描述

在二维平面上有 NN 个编号从 11 到 NN 的球,第 ii 个位于 (Xi,Yi)(X_i, Y_i)。其中,X=(X1,X2,⋯ ,Xn)X = (X_1, X_2, \cdots, X_n) 以及 Y=(Y1,Y2,⋯ ,Yn)Y = (Y_1, Y_2, \cdots, Y_n) 分别是一个 1,2,⋯ ,n1, 2, \cdots, n 的排列(译注:即横纵坐标分别两两不同)。

你可以执行任意次以下操作:

  • 从剩下的球中选择一个球,记为 kk。对剩下的每个球 ii,若满足「Xi<XkX_i < X_k 且 Yi<YkY_i < Y_k」或「Xi>XkX_i > X_k 且 Yi>YkY_i > Y_k」(译注:即两球坐标间有二维偏序关系),将其移除。

求操作结束后,可能的剩下球的集合的数量,对 998244353998244353 取模。

  • 1≤N≤3001 \le N \le 300

输入格式

第一行输入一个数字 NN,即球数。

之后 NN 行第 ii 行输入两个数字 XiX_i 和 YiY_i,即第 ii 个球的坐标。

输出格式

输出一个数字,代表取模后的答案。

Translated by hyperReality.

输入输出样例

  • 输入#1

    3
    1 3
    2 1
    3 2

    输出#1

    3
  • 输入#2

    4
    4 2
    2 1
    3 3
    1 4

    输出#2

    3

输入解题思路,AI测评打分。不知道怎么写?

首页