解释题目：Indoor Positioning
Most indoor positioning algorithms depend on accurate base station locations. However, in actual
scenarios, the cost of obtaining accurate base station locations is high. Many base stations are hidden
in the ceiling and cannot be measured. It is a difficult problem in the industry to locate users and sites
simultaneously by using only a few accurate sites and a large number of users’ delay measurements.
Consider a room as 20  20 meters square in 2D. The center of the room has the coordinate (0, 0).
There are four base stations (BS) and n user equipment (UE) devices located in the room. Both BSs and
UEs can be considered points inside the room. Base stations are located in four different quadrants of the
plane in the order shown in the image below.
You know the exact locations of the first two BSs, but you don’t know the locations of the remaining
two BSs as well as all UEs.
For each UE, you are given the time of arrival (ToA) in nanoseconds (ns) of signal from the UE to
each of the four base stations. ToA is measured on the base station and includes transmission delay
and noise. More information on how ToA is calculated can be found in the Test generation section
below.
Based on the given information, your task is to estimate the coordinates of the remaining two BSs
as well as all UEs as closely as possible to the actual positions.
Input
The first line contains a single integer n – the number of UEs.
The second line contains two space-separated floating-point numbers xbs;1 and ybs;1 – the coordinates
of the first BS.
The third line contains two space-separated floating-point numbers xbs;2 and ybs;2 – the coordinates
of the second BS.
The following n lines contain four space-separated floating-point numbers ti;1 ti;2 ti;3 ti;4 each,
denoting the measured time of arrival from the i-th UE to the corresponding BS.
1
Output
In the first line print two space-separated floating-point numbers xbs;3 and ybs;3 – the estimated
coordinates of the third BS.
In the second line print two space-separated floating-point numbers xbs;4 and ybs;4 – the estimated
coordinates of the fourth BS.
In the next n lines print estimated coordinates xue;i and yue;i of the corresponding UEs.
Constraints
20  n  200,
ti;j > 0,
xbs;1  0 and ybs;1  0,
xbs;2  0 and ybs;2  0,
xbs;3  0 and ybs;3  0,
xbs;4  0 and ybs;4  0,
􀀀10  xbs;i; ybs;i; xue;i; yue;i  10.
Notes
Sample test case
Check the following sample test case. Note that in this test case the number of UEs is less than
the allowed lower limit in the constraints (20). This test case is for demonstration purposes only and
is not included in the provisional or final test sets.
Input (stdin) Output (stdout)
7
-5.000 -5.000
7.000 -4.000
126.299 95.354 120.525 119.727
135.098 180.551 172.184 194.325
234.749 259.073 214.143 242.686
229.045 226.359 212.143 234.152
88.203 56.870 66.165 95.202
244.898 246.406 219.213 211.507
165.713 182.486 188.144 209.985
-0.657574772 2.202897216
9.612727847 7.184456177
6.052894344 -3.230646577
-6.258069892 -5.628141926
-7.630356154 8.287634824
0.906085783 0.813700552
5.519233285 -2.995729624
3.011525986 8.822308221
-0.400688838 -7.997504188
The actual positions of the four BSs are (-5, -5), (7, -4), (-2, 3) and (7, 9). There are 7 UEs in
positions (5, -4), (-5, -8), (-9, 7), (1, 1), (4, -1), (4, 6) and (1, -5). All actual and estimated positions
for this sample test case are shown on the image below.
2
Scoring
If your output for the test is invalid, i.e. the coordinates are missing, out of bounds of the room or
corresponding base station quadrant, your score for a test is 0. Otherwise, your score for the test is

(
1
1 + Dbs
+
1
1 + Due
)  5  106

where:
Dbs =
vuut
1
2
X4
i=3
(xbs;i 􀀀 ^xbs;i)2 + (ybs;i 􀀀 ^ybs;i)2
Due =
vuut
1
n
Xn
i=1
(xue;i 􀀀 ^xue;i)2 + (yue;i 􀀀 ^yue;i)2
(^xbs;i; ^ybs;i) – the actual coordinates of the BSs,
(^xue;i; ^yue;i) – the actual coordinates of the UEs.
The score for the sample test case above is 2918539.
Submissions
 The execution time limit is 4 seconds per test case and the memory limit is 1024 mebibytes.
 The code size limit is 64 kibibytes.
 The compilation time limit is 1 minute.
 Note that the sample data set in the zip file includes the input data and expected output data in the
sample directory. The end user must come up with an ideal algorithm to generate the estimated data set
and validate it against the expected data set. End users only need to submit the out_est.txt file. No code
should be submitted under any circumstances. A problem description must contain at least one sample
test case input along with a possible valid output. A sample input/output should be of considerably small
size for manual step-by-step analysis. A sample test case explanation contains related descriptions and
visualizations as well as scoring function calculations. Note that a sample output does not have to be
optimal, though it must be valid.
3
4
References
Four of the most popular methods: Chan’s [1], Foy’s [2], Fang’s [3] and Friedlander’s [4] can be
considered. These algorithms enable the calculation of the geographical position of a user equipment
using the time differences of arrival (TDoA) between several base stations and UE.
[1] Chan, Y.T., Ho, K.C.: A Simple and Efficient Estimator for Hyperbolic Location. IEEE Trans.
on Signal Proc. 42(8), 1905–1915 (1994)
[2] Foy, W.H.: Position-Location Solutions by Taylor-Series Estimation. IEEE Trans. on Aero.
and Elec. Systems AES-12(2), 187–194 (1976)
[3] Fang, B.T.: Simple Solution for Hyperbolic and Related Position Fixes. IEEE Trans. on Aero.
and Elec. Systems 26(5), 748–753 (1990)
[4] Friedlander, B.: A Passive Localization Algorithm and Its Accuracy Analysis. IEEE Jour. of
Oceanic Engineer. OE-12(1), 234–245 (1987)