Data Visualization: A scatter plot with overplotting counts

Draw a scatter plot on a character grid, showing how many points share each cell.

What to build

A program that draws points on a W × H grid and counts overlaps.

Requirements

  • Each point's column is int((x − xmin) / (xmax − xmin) × (W − 1) + 0.5) and its row int((y − ymin) / (ymax − ymin) × (H − 1) + 0.5); either is 0 when its values are all equal.
  • A cell with one point shows *, with 2 to 9 points the digit, with 10 or more #, and an empty cell .. Print the rows from the top (row H − 1) down, each starting with |, then + and W -.

Input

Line 1: W H. Line 2: n. Then n lines x y.

Output

H + 1 lines.

Constraints

2 ≤ W, H ≤ 40; 1 ≤ n ≤ 1000.

Example

Input:

5 3
4
0 0
4 2
2 1
2 1

Output:

|....*
|..2..
|*....
+-----

Why it works

Counting points per cell makes crowded areas visible, which a single mark per cell would hide, and flipping the rows puts larger y values higher up.

Examples

Example 1 · Input
5 3
4
0 0
4 2
2 1
2 1
Expected output
|....*
|..2..
|*....
+-----
Example 2 · Input
3 2
3
5 5
5 5
5 5
Expected output
|...
|3..
+---

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Count points per cell in a dictionary keyed by (row, column).

Hint 2

Row 0 is the bottom of the chart but the last line printed.

Solution

Show one correct solution (try it yourself first)
w, h = map(int, input().split())
n = int(input())
points = [tuple(map(float, input().split())) for _ in range(n)]
xs, ys = [p[0] for p in points], [p[1] for p in points]


def place(v, lo, hi, size):
    return 0 if hi == lo else int((v - lo) / (hi - lo) * (size - 1) + 0.5)


counts = {}
for x, y in points:
    cell = (place(y, min(ys), max(ys), h), place(x, min(xs), max(xs), w))
    counts[cell] = counts.get(cell, 0) + 1
for row in range(h - 1, -1, -1):
    line = ""
    for col in range(w):
        c = counts.get((row, col), 0)
        line += "." if c == 0 else "*" if c == 1 else str(c) if c < 10 else "#"
    print("|" + line)
print("+" + "-" * w)

Lesson: Scatter plots and correlation →