题目详情题解（0）讨论（0）提交记录（0）

AT_arc076_c.[ARC076E] Connected?

省选/NOI-

通过率：0%

AC君温馨提醒

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

题目描述

すぬけ君正在玩一个益智游戏。在这个益智游戏中，有一个 R×CR \times C 的矩形棋盘，棋盘上分别写有 11 到 NN 的每个整数各 22 次。整数 ii 写在坐标 (xi,1,yi,1)(x_{i,1}, y_{i,1}) 和 (xi,2,yi,2)(x_{i,2}, y_{i,2}) 上。

すぬけ君的目标是，对于所有 11 到 NN 的整数，将写有相同整数的两个格子用曲线连接起来。此时，曲线不能超出矩形的边界，也不能彼此相交。

请判断能否做到上述目标。

输入格式

输入以下格式，通过标准输入给出。

RR CC NN x1,1x_{1,1} y1,1y_{1,1} x1,2x_{1,2} y1,2y_{1,2} ⋯ xN,1x_{N,1} yN,1y_{N,1} xN,2x_{N,2} yN,2y_{N,2}

输出格式

如果すぬけ君能够达成目标，输出 YES；否则输出 NO。

输入输出样例

  • 输入#1

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

    输出#1

    YES

  • 输入#2

    2 2 4
0 0 2 2
2 0 0 1
0 2 1 2
1 1 2 1

    输出#2

    NO

  • 输入#3

    5 5 7
0 0 2 4
2 3 4 5
3 5 5 2
5 5 5 4
0 3 5 1
2 2 4 4
0 5 4 1

    输出#3

    YES

  • 输入#4

    1 1 2
0 0 1 1
1 0 0 1

    输出#4

    NO

说明/提示

限制条件

  • 1≤R,C≤1081 \leq R, C \leq 10^8
  • 1≤N≤1051 \leq N \leq 10^5
  • 0≤xi,1,xi,2≤R (1≤i≤N)0 \leq x_{i,1}, x_{i,2} \leq R\ (1 \leq i \leq N)
  • 0≤yi,1,yi,2≤C (1≤i≤N)0 \leq y_{i,1}, y_{i,2} \leq C\ (1 \leq i \leq N)
  • 给定的任意两个点都不同
  • 所有输入均为整数

样例解释 1

示意图 如上图所示，可以将每对整数相同的点用曲线连接起来，从而达成目标。

由 ChatGPT 5 翻译

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

首页