Finding a Right Isosceles Triangle
Time limit1sMemory limit128 MB
Given a 10x10 binary grid, decide whether the filled cells exactly form one axis-aligned right isosceles triangle and output its three vertices or 0.
- Level
Medium6 of 10
- Topics
- Geometry, Simulation, Implementation
- Solved
- No attempts yet
Problem
Each cell of a 10 by 10 grid contains either 0 or 1. Determine whether all cells containing 1 form exactly one filled right isosceles triangle.
At least one side of the triangle must be horizontal or vertical. Every cell on the boundary or inside the triangle must be filled with 1, and every other cell must be 0. The given shape may fail to be a triangle.
Input
The input consists of 10 lines. Each line contains exactly 10 characters with no spaces, and each character is either 0 or 1.
Output
If the given shape forms a right isosceles triangle, print the positions of its three vertices. Otherwise, print 0.
Print each vertex as two integers on its own line. The first integer is the row counted from the top, and the second integer is the column counted from the left. Print the vertices in increasing row order, breaking ties by increasing column order.