The God-Like Cow(GLC) was cutting problems about MST (minimum span tree) such as K-Degree Bounded MST
recently. For example, given n points stand for n villages and build some roads between villages.
The cost of building roads is the distance between the two villages. And to calculate the minimum cost
to build roads such that you can travel between any two villages is well known as the MST problem.
But in fact, we never bulid two roads which have common point except the point of villages.
Does the MST satisfy the condition that none of two tree edges have common point except the point
So baihacker wants to develop a problem to calculate the MST with the condition mentioned just now.
A force algorithm is to enumerate all the possible graphs and calculate the MST.
Some times, there are so many edges that it takes long time to solve the problem.
If there are 5 points, there are 10 edges and 2^10 possible graphs and some of them are valid.
But when n is 10, there are 45 edges and 2^45 possible graph and some them are valid.
So it is difficult to design the test cases.Here comes the problem.
Given n different points in the plane, and you can draw lines (needn't to be straight line(different
from the condition discussed just now), any simple curve will be ok) to link any two points with the restrictions:
1.The number of lines that links two points should be at most one;
2.Any pair of lines have no common point except when the common point is one of the given points.
How many lines can you draw at most?
Mutiple test cases.
For each test case:
The first line is one integer n(1<=n<=20).
In the next n lines, each line has two integers x, y (0<=x,y<=255)seperated by a space which is the coordinate
of a point.