QOJ.ac

QOJ

Limite de temps : 2 s Limite de mémoire : 1024 MB Points totaux : 100

#3814. 圣约翰节

Statistiques

波尔图的圣若昂节(Festa de São João)是欧洲最热闹的街头节日之一。节日的高潮是 6 月 23 日至 24 日的夜晚,从里贝拉(Ribeira)到福兹(Foz)整晚都有舞会。

这是一个与朋友、亲戚、邻居或街上的陌生人共同庆祝的时刻,人们手持彩色塑料锤、巨大的大蒜花或一束柠檬草,向路人致以亲切的问候。烟花、烤沙丁鱼、烧烤、篝火、盆栽罗勒(manjericos)以及从各个角落升起的、覆盖天空的白炽孔明灯(balões de S.João),使这个节日独具特色。

孔明灯由薄纸制成,必须充满热空气才能升空。有时它们会在地面上烧毁,或者在上升途中因突如其来的阵风而坠落。因此,成功的放飞者通常会带着焦虑和喜悦,注视着孔明灯的移动,直到它们在天空中消失不见。

我们不知道是否有任何尝试去打破孔明灯同时放飞的吉尼斯世界纪录(如果真的有,那对消防员来说可能是一个可怕的夜晚)。

你能想象吗?成千上万的人在城市公园准备放飞他们的孔明灯,这些孔明灯位于同时放飞的较大孔明灯区域内。

大型孔明灯可用于识别它们在天空中的位置,以便在观测时刻统计幸存的数量。

题目描述

给定大型孔明灯的位置和小型孔明灯的位置,确定有多少个小型孔明灯位于由任意三个大型孔明灯所定义的三角形的内部或边界上。

输入格式

第一行包含一个整数 $L$,表示观测时刻大型孔明灯的数量。接下来的 $L$ 行,每行包含一对由空格分隔的整数,表示一个大型孔明灯的坐标 $(x, y)$。之后,有一行包含一个整数 $S$,表示小型孔明灯的数量,随后是 $S$ 行,每行定义一个小型孔明灯的位置。高度对我们来说无关紧要。所有给定的点都是不同的,并且至少有三个代表大型孔明灯的点是不共线的。

输出格式

输出一行,包含位于由任意三个大型孔明灯所定义的三角形内部或边界上的小型孔明灯的数量。

数据范围

$3 \le L \le 10\,000$ 大型孔明灯的数量。 $1 \le S \le 50\,000$ 小型孔明灯的数量。 $0 \le x, y \le 2^{30}$ 坐标范围。

样例

样例输入 1

8
3 4
2 8
5 4
1 8
4 7
3 10
11 2
7 3
6
5 12
3 7
3 3
4 5
0 4
2 6

样例输出 1

3

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.