QOJ.ac

QOJ

时间限制: 1 s 内存限制: 1024 MB 总分: 100

#2703. 骑士的知识

统计

古代文明对地球和几何学有着巨大且大多出人意料的认识。在建造纪念碑时,他们不会随意选择地点。相反,每个建筑点都经过了仔细的选择和计算。如今,我们可以通过所谓的“地脉线”(ley lines)观察到这一点。地脉线是一条水平或垂直的无限长直线,它至少穿过两个古代纪念碑。地脉线被认为是某种魔法能量的来源,任何建在这样一条线上的教堂都被称为“强力教堂”(mighty church)。

目前已经存在一些纪念碑和教堂。一个古代文明正计划建造一座新的纪念碑,但地点尚未确定。他们正在寻找一个位置,使得该位置能将最多的普通教堂转化为强力教堂。新纪念碑可以与教堂或现有的纪念碑位于同一地点——在这种情况下,新纪念碑将直接建在教堂或纪念碑周围。

图 K.1:样例 2 的示意图,包含 2 条地脉线(|)、6 座纪念碑(■)、2 座强力教堂(⛪)以及 3 座在建造虚线纪念碑后转化为强力教堂的普通教堂(⛪)。

输入格式

输入包含: 一行,包含两个整数 $m$ 和 $c$ ($0 \le m, c \le 1000$),分别表示已建成的纪念碑和教堂的数量。 $m$ 行,每行包含纪念碑的坐标。 * $c$ 行,每行包含教堂的坐标。

所有坐标均为两个整数 $x$ 和 $y$ ($-10^6 \le x, y \le 10^6$)。给定的坐标对互不重合,但任何坐标都可能与新纪念碑的位置重合。

输出格式

输出三个整数:建造新纪念碑的坐标,以及通过这座新纪念碑将转化为强力教堂的普通教堂数量。坐标应在范围 ($-10^6 \le x, y \le 10^6$) 内。如果存在多个最优解,你可以输出其中任意一个。

样例

样例输入 1

2 3
0 5
5 0
0 1
0 3
3 0

样例输出 1

0 0
3

样例输入 2

6 5
-6 0
-4 0
-3 0
-4 -2
-3 -2
-2 -3
-6 -1
-4 -1
-3 -1
-5 -3
0 -3

样例输出 2

-6 -3
3

样例输入 3

1 2
0 0
1 0
0 1

样例输出 3

0 0
2

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.