Showing posts with label Online Judge. Show all posts
Showing posts with label Online Judge. Show all posts
Maximum Number of Points in a Line
Resources:
wikipedia.org ==>> Collinearity
GFG
How To Determine If Points Are Collinear In Coordinate Geometry?
Collinear
Maximum Number of Points in a Line
Implementation basis Spoj & Codechef problem:
1118 - Incredible Molecules
Problem link: 1118 - Incredible Molecules
Topic: Geometry
Resources:
Robert Eisele
Matrix.Code
Code:
2015 ACM Amman Collegiate Programming Contest ( H.Bridge)
Problem link: H. Bridges
Idea:
First, find all bridges in the given graph, then remove them from the graph and find all components of the resulting graph.
Consider each component as a single vertex and add the bridges again, now you have a tree where all edges are bridges (in the original graph).
In the resulting tree, to make an edge not a bridge, it has to be in a cycle, and since all edges in this cycle won't become bridges anymore, you have to create the largest possible cycle, so find the longest path in the tree, and connect it's endpoints. Final answer is : Total number of bridges — length of resulting cycle + 1
Which is equal to : Total number of bridges — longest path in tree.
Number of single cycle components in an undirected graph (CF-977E)
E. Cyclic Components
resource
হিন্টঃ প্রতিটি কম্পোনেন্ট এ চেক করবো তাদের প্রত্যেকটি নোডের ডিগ্রি দুই কিনা, যদি দুই হয় তাইলে সেটা একটা সিঙ্গেল সাইকেল কম্পোনেন্ট।
FACT0 - Integer Factorization (15 digits)