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

AT_abc402_d.[ABC402D] Line Crossing

普及/提高-

通过率：0%

AC君温馨提醒

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

题目描述

在圆周上等间距地排列着 NN 个点，按顺时针方向依次编号为 1,2,…,N1,2,\ldots,N。

有 MM 条互不相同的直线，其中第 ii 条直线通过两个不同的点：点 AiA_i 和点 BiB_i（1≤i≤M1 \leq i \leq M）。

请计算满足以下两个条件的整数对 (i,j)(i,j) 的个数：

  1. 1≤i<j≤M1 \leq i < j \leq M
  2. 第 ii 条直线与第 jj 条直线相交

输入格式

输入通过标准输入给出，格式如下：

NN MM
A1A_1 B1B_1
A2A_2 B2B_2
⋮\vdots
AMA_M BMB_M

输出格式

输出答案。

输入输出样例

  • 输入#1

    8 3
1 5
1 8
2 4

    输出#1

    2

  • 输入#2

    5 10
2 5
1 5
1 2
2 4
2 3
1 3
1 4
3 5
3 4
4 5

    输出#2

    40

说明/提示

约束条件

  • 2≤N≤1062 \leq N \leq 10^6
  • 1≤M≤3×1051 \leq M \leq 3 \times 10^{5}
  • 1≤Ai<Bi≤N1 \leq A_i < B_i \leq N（1≤i≤M1 \leq i \leq M）
  • (Ai,Bi)≠(Aj,Bj)(A_i,B_i) \neq (A_j,B_j)（i≠ji \neq j）
  • 输入中的所有数值均为整数

样例解释 1

如图所示，圆周上有 88 个点和 33 条直线：

  • 第 11 条直线与第 22 条直线相交
  • 第 11 条直线与第 33 条直线不相交
  • 第 22 条直线与第 33 条直线相交

满足条件的整数对为 (i,j)=(1,2),(2,3)(i,j)=(1,2),(2,3)，因此输出 22。

翻译由 DeepSeek V3 完成

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

首页