ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

NEERC, Eastern subregion, Yekaterinburg, October 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Abstract Thinking

Time limit: 1.0 second
Memory limit: 64 MB
This summer programmer Dima wanted to take a rest from programming because he felt that the level of abstraction his profession required was driving him mad. He decided to go to Greece. But he forgot that Greece was the homeland of geometry where famous Euclid lived and worked. In geometry, instead of real figures, abstract notions are studied, and the proofs are based not on intuition, but on axioms and formal definitions. Even shepherds in Greece have well-developed abstract thinking skills.
For example, consider the following problem, which will show the level of your abstract thinking abilities. Imagine a circle, then put mentally n points on its periphery at equal distances. After that connect (again mentally!) these points pairwise by straight segments (of course, you remember that such segments are called chords).
Now consider any three different chords from this set that intersect pairwise. If at least one of their intersection points lies inside the circle, we will call the figure formed by these chords an interesting triangle. If you can count the number of interesting triangles correctly, then you can go to Greece and not be ashamed of yourself there.


You are given the number n of points on the periphery of a circle (3 ≤ n ≤ 2000).


Output the number of interesting triangles.


Problem Author: Denis Musin
Problem Source: ACM ICPC 2007–2008. NEERC. Eastern Subregion. Yekaterinburg, October 27, 2007
To submit the solution for this problem go to the Problem set: 1591. Abstract Thinking