Find the co-ordinates of missing polygon

Revision en1, by rockshivam999, 2021-08-18 08:33:26

Glass Piece Problem Description A square glass sheet of size 'S' cm fell down and broken down into N+1 pieces. A man collected the broken pieces and he is trying to arrange the pieces to get the original shape. He found that exactly one piece is missing. To find the exact position of the missing piece, he noted down all (x,y) coordinates of each broken piece. Please help him to find the coordinates of the missing piece. Note 1 : The input order of corners of known glass pieces are in the clockwise direction starting from the corner having least X value. If more than one corners having the same least X value, then start from the corner having least X and least Y value. Note 2 : The corners of missing glass piece should output in the clockwise direction starting from the corner having least X value. If more than one corners have same least X value, then start from the corner having least X and least Y value. Constraints 1 < S <= 1000. 1 < N <= 50. Input Format First line contains an integer, S, size of Glass Sheet. Second line contains an integer, N. Next N lines contain set of space separated integers indicates the details of N known glass pieces as follows: · First number indicates total corners of that glass piece — say i, · followed by 2 * i integers denotes X and Y coordinates of i corners, delimited by space Output Coordinates of missing piece in (X,Y) format separated by spaces. Test Case Explanation Example 1 Input 400 3 5 0 0 200 0 400 200 100 250 0 250 3 200 0 400 0 400 200 4 100 250 400 200 400 400 200 400 Output (0,250) (100,250) (200,400) (0,400) Explanation The size of the square glass plate is 400 cm * 400 cm. The glass plate broke into 4 pieces and he got 3 pieces.

Tags #newproblem, #math, computational geometry,, computational-geometry

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English rockshivam999 2021-08-18 08:33:26 1821 Question is from old codevita and I was trying to solve it for practice but facing issue please some one help (published)