{"problem":{"name":"Net of Net","description":{"content":"For a three-dimensional convex polytope $P$, the **net** of it is the set of (possibly overlapping) polygons satisfying the following. *   Each polygon corresponds one-to-one with a face of $P$. *   ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":10000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"1202Contest_g"},"statements":[{"statement_type":"Markdown","content":"For a three-dimensional convex polytope $P$, the **net** of it is the set of (possibly overlapping) polygons satisfying the following.\n\n*   Each polygon corresponds one-to-one with a face of $P$.\n*   $P$ can be constructed by repeating the operation of folding along its edges.\n\nHere, folding along an edge is the following operation:\n\n*   Choose an edge, the removal of which would make the current figure disconnected. Use the line defined by this edge as the axis of rotation and rotate the entire part of the current figure that lies on one side of this edge by any angle (in three dimensions). If necessary, vertices or edges that coincide exactly in coordinates are identified.\n\nSimilarly, the **net of the net** of $P$ is the set of line segments satisfying the following.\n\n*   Each edge corresponds one-to one with an edge of the net of $P$.\n*   The net of $P$ can be constructed by repeating the operation of folding along its vertices.\n\nHere, folding along a vertex is the following operation:\n\n*   Choose a vertex, the removal of which would make the current figure disconnected. Use this vertex as the center of rotation and rotate the entire part of the current figure that lies on some side of this vertex by any angle (in two dimentions). If necessary, vertices that coincide exactly in coordinates are identified.\n\nYou are given $N$ points on the unit sphere such that no four of these are on the same plain. The coordinate of $i$\\-th point is given by $(x_i,y_i,(-1)^{c_i}\\sqrt{1-x_i^2-y_i^2})$.\nDetermine whether there exists a net of a net of the convex hull of given points, which is a path. If exists, compute the largest length of such path.\n\n## Constraints\n\n*   $4 \\leq N \\leq 14$\n*   $-1\\leq x_i,y_i\\leq 1$\n*   $c_i$ is $0$ or $1$\n*   $x_i^2+y_i^2\\leq 1$\n*   No two given points coincide.\n*   For all four different given points $p,q,r,s$, the distance between $s$ and the plain on which $p,q,r$ exist is at least $10^{-5}$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$x_1$ $y_1$ $c_1$\n$\\vdots$\n$x_N$ $y_N$ $c_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"1202Contest_g","tags":[],"sample_group":[["4\n0.000000 0.000000 1\n0.000000 0.000000 0\n1.000000 0.000000 1\n0.000000 1.000000 0","13.899494936612\n\nThe following net of net is optimal.\n\n![image](https://img.atcoder.jp/DEGwer2023/G_zu.png)Figure: the optimal net of the net."],["6\n-0.322191 -0.852465 0\n-0.463288 -0.553583 1\n0.378710 -0.346882 1\n-0.489727 0.488028 0\n-0.731142 0.227066 1\n0.254757 -0.899035 0","22.950966056549"],["8\n0.837078 0.492956 1\n0.360579 -0.565500 0\n-0.367448 -0.492394 1\n0.491637 -0.658814 1\n-0.505114 -0.538563 1\n0.544637 0.592884 1\n-0.622207 -0.379934 1\n0.402129 0.684158 1","28.879053537910"],["4\n0.800000 0.600000 0\n1.000000 0.000000 1\n-0.280000 -0.960000 1\n0.000000 0.000000 0","13.284042973728"]],"created_at":"2026-03-03 11:01:13"}}