邮局 - 题目

给你地球上所有邮局的位置，以及一系列需要寄送的包裹的目的地。对于每个包裹，你需要找到最适合作为该包裹目的地的邮局的最大集合——即该邮局集合必须满足以下约束条件：

为了便于计算，本题中将地球近似为一个半径为 $6381\text{ Km}$ 的完美球体。两点之间的距离可以使用半正矢公式（haversine formula）计算：

$$A = \sin^2((lat1-lat2)/2) + \cos(lat1) \cdot \cos(lat2) \cdot \sin^2((long1-long2)/2)$$

$$DISTANCE = 6381 \cdot 2 \cdot \operatorname{atan2}(\sqrt{A}, \sqrt{1-A})$$

（如果你愿意，也可以使用其他公式，但请注意，反余弦公式在微小距离下会产生较大的舍入误差，从而可能导致错误的结果）。

输入文件是一个二进制文件；其中写入的所有数字均采用小端序（little-endian）表示。它按以下顺序包含：

$4$ 字节，表示邮局数量 $N$ —— 整数，不超过 $3\,000\,000$。
对于每个邮局，输入文件包含两个数字 <LAT LONG>（每个 $4$ 字节），表示该邮局的纬度和经度（以度为单位）。这些数字是单精度 IEEE754 浮点数。所有纬度均在 $-90$ 到 $90$ 度之间；所有经度均在 $-180$ 到 $180$ 度之间。
$4$ 字节，表示包裹数量 $M$ —— 整数，不超过 $500\,000$。
对于每个包裹，输入文件包含两个数字 <LAT LONG>（每个 $4$ 字节），表示目的地的纬度和经度（以度为单位）。这些数字是单精度 IEEE754 浮点数。所有纬度均在 $-90$ 到 $90$ 度之间；所有经度均在 $-180$ 到 $180$ 度之间。

输出文件也是一个二进制文件，仅包含以小端序（little-endian）表示的 32 位整数。对于输入文件中的 $M$ 个包裹，每个包裹对应输出：

一个整数 —— 目的地集合中的邮局数量 $P$。
$P$ 个整数 —— 目的地集合中邮局的索引，按升序排序（较小的索引在前）。输入文件中第一个邮局的索引视为 $1$（因此，所有索引应在 $1$ 到 $N$ 之间，包含端点）。

N/A - 二进制文件

N/A - 二进制文件

QOJ.ac