Elden Ring Laser Escape

BaoBao is playing the famous game Elden Ring these days. In this open‐world game, she controls her character to travel from place to place. However, her character can easily fall into traps. Right now, the character is stuck on a 2-dimensional plane with deadly lasers. There are \( n \) laser generators (each represented by a point) that emit laser beams: every pair of generators is connected by a beam (thus there are \( \frac{n(n-1)}{2} \) beams in total). Note that each beam is a line segment that starts and ends exactly at generator points and does not extend to infinity.

Starting at point \( (0,0) \), BaoBao wishes to escape to \( \left(10^{10^{10^{10^{10}}}},\;10^{10^{10^{10^{10}}}}\right) \) without touching any laser beam or generator. In order to do so, she can ask her friend DreamGrid to remove any number of laser generators (and, consequently, all beams incident to any removed generator). Your task is to compute the minimum number of generators that must be erased so that there exists a laser‐free path from \( (0,0) \) to \( \left(10^{10^{10^{10^{10}}}},\;10^{10^{10^{10^{10}}}}\right) \).

Note: BaoBao does not need to move in a fixed direction. Her escape route can be any continuous curve as long as it does not touch any remaining generator or beam.

inputFormat

The first line contains an integer \( n \) (the number of laser generators). Each of the following \( n \) lines contains two space‐separated integers \( x \) and \( y \) representing the coordinates of a generator.

You can assume \( n \ge 0 \) and \( (0,0) \) is not the location of any generator.

outputFormat

Output a single integer: the minimum number of generators that need to be removed so that there exists a path from \( (0,0) \) to \( \left(10^{10^{10^{10^{10}}}},\;10^{10^{10^{10^{10}}}}\right) \) which does not touch any remaining generator or laser beam.

Explanation: A necessary and sufficient condition for a safe escape is that, after removals, there exists a vector \( v \) such that \( v \cdot p > 0 \) for every remaining generator \( p \). Equivalently, all remaining points lie strictly in an open half‐plane determined by a line through \( (0,0) \). The answer is \( n \) minus the maximum number of generators that can be kept satisfying this condition.

sample

1
1 1

0