How many segments can be obtained from N points? How many different triangles can be obtained from N segments?

B

bazeyvit2012-12-19 19:24:03

Python

bazeyvit, 2012-12-19 19:24:03

Are there any formulas in which you can put the number N and get the answer?
All this I need to solve this problem:

A set of points with integer coordinates is given on the plane. It is necessary to find a triangle of the largest area with vertices at these points, one side of which lies on the x-axis. If there are no such triangles, then output "there are none"

If you also help with the task, for example, by suggesting a different solution, many thanks to you from me.

Reply

Answer the question

In order to leave comments, you need to log in

3 answer(s)

Y

yeputons, 2012-12-19
@bazeyvit

From N points you can get N*(N-1)/2 different pairs ( C from N by 2 ) The lengths may be different, but this is not treated without knowing the specific points.
About triangles, the situation is similar, but you need to choose three segments - M * (M-1) * (M-2) / 6, where M is the number of segments. If you just need the number of triangles from the given points, then there will be N * (N-1) * (N-2) / 6.
It turns out from the considerations we select the first point in N ways, the second - N-1, the third - N-2 (because the previous ones have already been selected). It is necessary to divide by 6=3!, because each permutation of three points was received exactly once.
I do not really understand how this can be in this particular task.
But this observation will definitely help: S=len*h/2, where len is the length of the base, h is the corresponding height. Because the base lies on Ox, you need to find the longest segment on this axis (max-min) and the point farthest from Ox in order to maximize the height.

S

SabMakc, 2012-12-20
@SabMakc

If one side of the triangle lies on the X axis, then the problem is reduced to finding the largest segment lying on the given axis and the point that is as far as possible from this axis.

D

daeto, 2012-12-20
@daeto

In my opinion, this task is about filtering and finding the maximum / minimum. Obviously, such a triangle (if it is not degenerate) consists of:
1. A point on Ox that has a minimum x-coordinate
2. A point on Ox that has a maximum x-coordinate
3. A point not on Ox that has a maximum y-coordinate in absolute value
Such a search is done in one pass through the points.