DMOPC '20 Contest 7 P2 - Alice and Tiles

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 2.0s
Java 5.0s
Python 5.0s
Memory limit: 256M
Python 512M

Author:
Problem types

Alice is feeling bored in math class. So she gets an infinitely large sheet of graph paper and starts tiling it with squares and octagons, as shown below. The squares are 1 unit high, the octagons are 3 units high and 3 units wide, and all the tiles' vertices are at integer lattice points. The origin point, (0,0), is at the bottom-left corner of a square tile.

When Alice finally finishes tiling the infinitely large sheet of paper, math class is still not over. So she decides to colour in N tiles to make a single polygon with no holes. What are the polygon's vertices, in clockwise order?

Constraints

1 \le N \le 2 \times 10^5

-10^9 \le x_i, y_i \le 10^9

Subtask 1 [70%]

1 \le N \le 5 \times 10^4

Subtask 2 [30%]

No additional constraints.

Input Specification

The first line contains an integer N, the number of coloured tiles.

The next N lines each contain 2 integers x_i and y_i, the coordinates of the i-th coloured tile. If the tile is a square, these coordinates indicate its bottom-left corner. If it is an octagon, they indicate the bottom-left corner of its central square.

All tile coordinates are guaranteed to be valid, and the coloured tiles are guaranteed to form a single polygon with no holes.

Output Specification

On the first line, output K, the number of vertices of the coloured polygon.

On the j-th of the next K lines, output the x and y coordinates of the j-th vertex. The vertices should be outputted in clockwise order (in other words, if you imagine walking from one vertex to the next, the polygon should always be to your right). You must start with the vertex with the least x coordinate, breaking ties by choosing the vertex with the least y coordinate.

Sample Input 1

1
2 0

Sample Output 1

8
1 0
1 1
2 2
3 2
4 1
4 0
3 -1
2 -1

Sample Input 2

4
2 0
4 0
6 0
4 -2

Sample Output 2

18
1 0
1 1
2 2
3 2
4 1
5 1
6 2
7 2
8 1
8 0
7 -1
6 -1
6 -2
5 -3
4 -3
3 -2
3 -1
2 -1

Explanation for Sample 2

This case corresponds to the diagram provided in the problem statement.


Comments


  • 0
    tortle  commented on June 23, 2021, 11:03 p.m.

    Could someone help me debug my code? Its here: https://pastebin.pl/view/dd1e1001

    I'm getting the following error from visual studio: https://ibb.co/tYgLbxR

    Due to my poor knowledge of c++, I'm not sure why. enlighten me. If anyone needs me to explain the code a bit more, my discord is *-*#0325.

    Thanks!


    • 2
      julian33  commented on June 24, 2021, 12:06 a.m.

      in c++, pairs aren't hashable by default. unordered maps hash the keys, and since your key is a pair, it gives you an error. You can fix this by changing the unordered_map to a map, or creating your own hash for a pair. Other than that, your code is very close to being correct, there is one very small tweak you need to make to receive AC.


      • 0
        tortle  commented on June 24, 2021, 1:22 a.m.

        Thank you so much! That's good to know. I changed it to map (and then fixed another thing) and it worked.