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

Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. Intersect Until You're Sick of It

Time limit: 0.5 second
Memory limit: 64 MB
Ural contests usually contain a lot of geometry problems. Many participants do not conceal their discontent with such disbalance. Still, we have decided not to break the tradition and give you an unbalanced contest. Let’s start!
Consider an iterative process for a set of points on a plane. Every iteration consists of three steps:
  1. Draw a line through every pair of different points.
  2. Find all intersections of all pairs of different non-parallel lines.
  3. Merge the initial set of points with the set of intersection points and go to step one.
After each iteration, the number of points either increases or stays the same.
You are given a set of points. Iterations repeat while the number of points increases. How many points will be in the set after the end of this iterative process?


The first line contains an integer n (1 ≤ n ≤ 100000). Further input describes n different points. For every point, you are given a pair of integer coordinates whose absolute value does not exceed 108.


If the process is infinite, print “oo” (two lowercase Latin letters ‘o’), otherwise print the number of points in the set after the end of the process.


0 0
0 1
1 0
1 1
Problem Author: Mikhail Rubinchik
Problem Source: Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014
To submit the solution for this problem go to the Problem set: 2036. Intersect Until You're Sick of It