Worst Picture

AtCoder

IDabc301_g

Time4000ms

Memory256MB

Difficulty—

There are $N$ people in a three-dimensional space. The $i$\-th person is at the coordinates $(X_i,Y_i,Z_i)$. All people are at different coordinates, and we have $X_i>0$ for every $i$. You will choose a point $p=(x,y,z)$ such that $x<0$, and take a photo in the positive $x$\-direction. If the point $p$ and the positions $A, B$ of two people are on the same line in the order $p,A,B$, then the person at $B$ will not be in the photo. There are no other potential obstacles. Find the number of people in the photo when $p$ is chosen to minimize this number. ## Constraints * $1 \leq N \leq 50$ * $0 < X_i \leq 1000$ * $-1000 \leq Y_i,Z_i \leq 1000$ * The triples $(X_i,Y_i,Z_i)$ are distinct. * All values in the input are integers. ## Input The input is given from Standard Input in the following format: $N$ $X_1$ $Y_1$ $Z_1$ $\vdots$ $X_N$ $Y_N$ $Z_N$ [samples]

Samples

Input #1

Output #1

2

For instance, if you take the photo from the point $(-0.5,-0.5,-0.5)$, it will not show the second person.

Input #2

Output #2

4

If you take the photo from the point $(-1,0,0)$, it will show four people.

API Response (JSON)

{
  "problem": {
    "name": "Worst Picture",
    "description": {
      "content": "There are $N$ people in a three-dimensional space. The $i$\\-th person is at the coordinates $(X_i,Y_i,Z_i)$.   All people are at different coordinates, and we have $X_i>0$ for every $i$. You will choo",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc301_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ people in a three-dimensional space. The $i$\\-th person is at the coordinates $(X_i,Y_i,Z_i)$.  \nAll people are at different coordinates, and we have $X_i>0$ for every $i$.\nYou will choo...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments