QOJ.ac

QOJ

시간 제한: 1 s 메모리 제한: 256 MB 총점: 100

#1412. JOI 海报

통계

K 理事长正在设计 3 张海报,以支持国际信息学奥林匹克(IOI)日本代表团。海报上计划分别印有字母 "J"、"O"、"I"。K 理事长已经迅速完成了字母 "J" 和 "I" 的海报,现在他打算以澳大利亚的星空为背景来设计剩下的字母 "O" 的海报。

海报是一个宽为 $W$、高为 $H$ 的矩形,左下角坐标为 $(0, 0)$,右上角坐标为 $(W, H)$。海报上印有 $N$ 颗星星。第 $i$ 颗星星 $S_i$ ($1 \le i \le N$) 在海报上的坐标为 $(X_i, Y_i)$,任意两颗星星的坐标均不相同。

K 理事长在设计字母 "O" 时,提出了以下想法:从 $N$ 颗星星中选择 4 颗不同的星星,分别记为 $A, B, C, D$。以 $A$ 为圆心且经过 $B$ 的圆记为圆 $O_1$,以 $C$ 为圆心且经过 $D$ 的圆记为圆 $O_2$。如果这两个圆 $O_1, O_2$ 同时满足以下两个条件,则这 4 颗星星 $A, B, C, D$ 的组合就是 K 理事长设计方案的一个候选:

  • 圆 $O_1$ 内部包含圆 $O_2$。也就是说,圆 $O_2$ 的内部或圆周上的任意一点都在圆 $O_1$ 的内部(不包括圆周上)。
  • 两个圆都不超出海报的矩形区域。也就是说,对于圆内部或圆周上的任意一点 $(X, Y)$,都满足 $0 \le X \le W$ 且 $0 \le Y \le H$。

问:共有多少种选择 4 颗星星 $A, B, C, D$ 的方法,使得它们能成为 K 理事长设计方案的候选?

课题

给定海报的大小和星星的信息,编写一个程序,求出有多少种选择 4 颗星星 $A, B, C, D$ 的方法,使其成为 K 理事长设计方案 of 候选。

输入格式

从标准输入中读取以下内容:

  • 第一行包含三个空格分隔的整数 $N, W, H$,分别表示海报上印有的星星数量、海报的宽度和高度。
  • 接下来的 $N$ 行中,第 $i$ 行($1 \le i \le N$)包含两个空格分隔的整数 $X_i, Y_i$($0 \le X_i \le W$ 且 $0 \le Y_i \le H$),表示星星 $S_i$ 在海报上的坐标。

输出格式

向标准输出输出一行,包含一个整数,表示满足 K 理事长设计方案候选条件的 4 颗星星 $A, B, C, D$ 的选择方法总数。

数据范围

所有输入数据均满足以下条件:

  • $4 \le N \le 50$
  • $1 \le W \le 1000$
  • $1 \le H \le 1000$
  • $0 \le X_i \le W$
  • $0 \le Y_i \le H$
  • 任意两颗星星的坐标均不相同。

子任务

官方测试数据包含 10 个独立的子任务。

子任务 1 [80 分]

  • 无论如何选择 4 颗星星 $A, B, C, D$,圆 $O_1$ 和圆 $O_2$ 均不相切。

子任务 2 [20 分]

  • 无附加限制。

样例

输入格式 1

7 20 15
9 5
13 9
15 13
7 4
6 8
14 7
16 7

输出格式 1

3

说明

该样例对应下图。星星 $S_i$ 用点 $i$ 表示。

在此图中,满足 K 理事长设计方案候选条件的 4 颗星星 $A, B, C, D$ 的选择方法共有 3 种。每种情况下的圆 $O_1, O_2$ 如下图所示:

请注意,在第三幅图中,圆 $O_1$ 和圆 $O_2$ 并不相切。

输入格式 2

15 20 30
11 8
14 25
3 20
1 27
2 16
12 8
0 4
3 10
12 11
5 9
16 3
2 13
4 24
18 3
12 28

输出格式 2

12

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
EditorialOpen Official EditorialQingyu- Download

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.