I got hints that this is a problem of Euler path, and distinct connected component but the given note says we can overwrite already made lines…
This is confusing.
Also i can’t implement the Euler path algotihm.
can you please share the code?
Note: Drawing a line which is already drawn, doubles the width of line and thus it can be added to specifications, i.e. if a line is drawn again, it is treated as a distinct line in the specifications. Also, in the given specifications, no three points are collinear.
Implementation of Shakshi and Art
@utkarsh.lal9430310535 hey here is code for euler path algo:https://ideone.com/whW86r
Logic behind this question is:
Consider this as a graph(lines as edges and points as nodes). We need to add edges, such that there is a Euler Path. Let C1, C2, C3 ,C4 … Ck be connected components of graph. Count the number of vertices(count of the open ends) with odd degree. If there is no vertex with odd degree, in a connected component, consider that there are two open ends, so add two to the count. You can leave atmost two open ends unpaired. That means, the number of pairings that need to be done are the minimum number of edges to be added.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.