{"problem":{"name":"Make Many Triangles","description":{"content":"There are $N$ distinct points on a two-dimensional plane. The coordinates of the $i$\\-th point are $(x_i,y_i)$. We want to create as many (non-degenerate) triangles as possible using these points as t","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc173_b"},"statements":[{"statement_type":"Markdown","content":"There are $N$ distinct points on a two-dimensional plane. The coordinates of the $i$\\-th point are $(x_i,y_i)$.\nWe want to create as many (non-degenerate) triangles as possible using these points as the vertices. Here, the same point cannot be used as a vertex of multiple triangles.\nFind the maximum number of triangles that can be created.\nWhat is a non-degenerate triangle? A non-degenerate triangle is a triangle whose three vertices are not collinear.\n\n## Constraints\n\n*   $3 \\leq N \\leq 300$\n*   $-10^9 \\leq x_i,y_i \\leq 10^9$\n*   If $i \\neq j$, then $(x_i,y_i) \\neq (x_j,y_j)$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$x_1$ $y_1$\n$x_2$ $y_2$\n$\\vdots$\n$x_{N}$ $y_{N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc173_b","tags":[],"sample_group":[["7\n0 0\n1 1\n0 3\n5 2\n3 4\n2 0\n2 2","2\n\nFor example, if we create a triangle from the first, third, and sixth points and another from the second, fourth, and fifth points, we can create two triangles.\nThe same point cannot be used as a vertex for multiple triangles, but the triangles may have overlapping areas."],["3\n0 0\n0 1000000000\n0 -1000000000","0"]],"created_at":"2026-03-03 11:01:14"}}