A11752 | Death Stars (hard)

The first line of the input contains an integer $N$ ( $1000<=N<=50000$ ) – the number of Death Stars. The second line of the input contains an integer $N_{1}$ ( $N<=N_{1}<=1.5·N$ ) – the number of stars in the first map. The next $N_{1}$ lines specify the coordinates of the stars in the first map. The $i$ -th line contains two space-separated floating-point numbers $x_{i}$ and $y_{i}$ with two decimal digits of precision each, representing the coordinates of the $i$ -th star in the first map.

The next line of the input contains an integer $N_{2}$ ( $N<=N_{2}<=1.5·N$ ) – the number of stars in the second map. The next $N_{2}$ lines contain locations of the stars in the second map, given in the same format as for the first map.

无

The tests are generated in the following way:

- The number of Death Stars $N$ is pre-selected in some way.
- The numbers of stars on the first and on the second map, $N_{1}$ and $N_{2}$ , are selected uniformly at random between $1.0×N$ and $1.5×N$ .
- $N$ Death Stars are generated at random, with coordinates between $-10000$ and $10000$ .
- Additional $N_{1}-N$ and $N2-N$ stars for the first and for the second map respectively are generated in the same way.
- A translation vector $(dx,dy)$ is generated, with $dx$ and $dy$ selected uniformly at random between $-10000$ and $10000$ . Each point in the first map is translated by $(dx,dy)$ .
- A rotation angle $θ$ is generated, with $θ$ selected uniformly at random between $0$ and $2π$ . Each point in the first map is rotated by an angle of $θ$ around the origin.
- Translations and rotations for the second map are generated and applied in the same way.
- The order of points is randomly permuted for both maps.
- The test case is saved, with each point written with two decimal digits of precision.