P8683 - Global Positioning System

内存限制：128 MB 时间限制：1 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：3 通过：2

Global Positioning System (GPS) is based on

n

artificial satellites, where each satellite has a 3D-coordinates

(x, y, z)

. Since the coordinates are always changing, we can hardly know the exact value of the coordinates, even if the satellites are relative static to each other.

To get more information about their coordinate, we still try every effort to do

m

measurements. For each measurement, we choose the

u

-th and the

v

-th satellites, and measure the coordinate difference between them. Specifically, we will get

x_v - x_u, y_v - y_u, z_v - z_u)

after the measurement of them. With these

m

measurement results, we can now know the coordinate difference between any two satellites.

However, lzr010506 has the impression that he has mistaken exactly one measurement result, so there may exist no possible coordinates to match all the measurements for the satellites for now. You need to find out all the measurements results that might be mistaken, so he can try to fix it as soon as possible.

Here a measurement result might be mistaken iff there exist possible coordinates to match all the measurements after modifying the mistaken measurement result to the one other than the original one.

The first line contains two integers  $n$   $(2≤n≤500000)(2\le n\le 500\,000)$  and  $m$   $(n−1≤m≤500000)(n-1\le m\le 500\,000)$ , denoting the number of the satellites that form the GPS and the number of the measurements that we have made.
The following  $m$  lines decribe the  $m$  measurements. Each of the  $m$  lines contains five integers  $u, v$   $(1≤u,v≤n,u≠v)(1\le u,v\le n, u \neq v)$ ,  $x, y$  and  $z$   $\times 10^9 \le x,y,z \le 2 \times 10^9)$ , which means that the measurement result between the  $u$ -th and the  $v$ -th satellites is  $(x, y, z)$ .
It is guaranteed that any (unordered) pair of satellites will not be measured more than once, and at least one measurement result might be mistaken.

The first line contains a single integer  $k$ , denoting the number of the measurements results that might be mistaken.
The second line contains  $k$  integers, denoting the indices of the measurement results that might be mistaken in increasing order.

3 3
1 2 3 3 3
1 3 1 1 1
2 3 -3 -2 -3

3
1 2 3

In the first sample test case, you can modify the first measurement result to  $(4, 3, 4)$ , or modify the second measurement result to  $(0, 1, 0)$ , or modify the third measurement result to  $(- 2, - 2, - 2)$ .

2022 牛客9

8683: Global Positioning System

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签