{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch2\u003eProblem H\n\u003c/h2\u003e\n\n\u003cp\u003e\nThe machine tool technology never stops its development. One of the recent proposals is more flexible lathes in which not only the workpiece but also the cutter bit rotate around parallel axles in synchronization. When the lathe is switched on, the workpiece and the cutter bit start rotating at the same angular velocity, that is, to the same direction and at the same rotational speed. On collision with the cutter bit, parts of the workpiece that intersect with the cutter bit are cut out.\n\u003c/p\u003e\n\n\u003cp\u003e\nTo show the usefulness of the mechanism, you are asked to simulate the cutting process by such a lathe.\n\u003c/p\u003e\n\n\u003cp\u003e\nAlthough the workpiece and the cutter bit may have complex shapes, focusing on cross sections of them on a plane perpendicular to the spinning axles would suffice. We introduce an $xy$-coordinate system on a plane perpendicular to the two axles, in which the center of rotation of the workpiece is at the origin $(0, 0)$, while that of the cutter bit is at $(L, 0)$. You can assume both the workpiece and the cutter bit have polygonal cross sections, not necessarily convex.\n\u003c/p\u003e\n\n\u003cp\u003e\nNote that, even when this cross section of the workpiece is divided into two or more parts, the workpiece remain undivided on other cross sections. \n\u003c/p\u003e\n\n\u003cp\u003e\nWe refer to the lattice points (points with both $x$ and $y$ coordinates being integers) strictly inside, that is, inside and not on an edge, of the workpiece before the rotation as \u003ci\u003epoints\u003c/i\u003e of interest, or POI in short.\n\u003c/p\u003e\n\n\u003cp\u003e\nOur interest is in how many POI will remain after one full rotation of 360 degrees of both the workpiece and the cutter bit. POI are said to remain if they are strictly inside the resultant workpiece. Write a program that counts them for the given workpiece and cutter bit configuration.\n\u003c/p\u003e\n\n\u003cp\u003e\nFigure H.1(a) illustrates the workpiece (in black line) and the cutter bit (in blue line) given in Sample Input 1. Two circles indicate positions of the rotation centers of the workpiece and the cutter bit. The red cross-shaped marks indicate the POI.\n\u003c/p\u003e\n\n\u003cp\u003e\nFigure H.1(b) illustrates the workpiece and the cutter bit in progress in case that the rotation direction is clockwise. The light blue area indicates the area cut-off.\n\u003c/p\u003e\n\n\u003cp\u003e\nFigure H.1(c) illustrates the result of this sample. Note that one of POI is on the edge of the resulting shape. You should not count this point. There are eight POI remained.\n\u003c/p\u003e\n\n\u003ccenter\u003e\n\u003cimg src\u003d\"CDN_BASE_URL/b4c44f6f30cc729c5c95de9576c0d25c?v\u003d1715203046\"\u003e\u003cbr\u003e\n\u003cp\u003e\nFigure H.1. The workpiece and the cutter bit in Sample 1\n\u003c/p\u003e\n\n\n\u003c/center\u003e\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\n\u003cp\u003e\nThe input consists of a single test case with the following format.\u003cbr\u003e\n\u003cbr\u003e\n\n$M$ $N$ $L$\u003cbr\u003e\n$x_{w1}$ $y_{w1}$\u003cbr\u003e\n...\u003cbr\u003e\n$x_{wM}$ $y_{wM}$\u003cbr\u003e\n$x_{c1}$ $y_{c1}$\u003cbr\u003e\n...\u003cbr\u003e\n$x_{cN}$ $y_{cN}$\u003cbr\u003e\n\u003cbr\u003e\n\nThe first line contains three integers. $M$ is the number of vertices of the workpiece $(4 \\leq M \\leq 20)$\nand $N$ is the number of vertices of the cutter bit $(4 \\leq N \\leq 20)$. $L$ specifies the position of the\nrotation center of the cutter bit $(1 \\leq L \\leq 10000)$.\n\u003c/p\u003e\n\n\u003cp\u003e\nEach of the following $M$ lines contains two integers. The $i$-th line has $x_{wi}$ and $y_{wi}$, telling that the position of the $i$-th vertex of the workpiece has the coordinates $(x_{wi}, y_{wi})$. The vertices are given in the counter-clockwise order.\n\u003c/p\u003e\n\n\u003cp\u003e\n$N$ more following lines are positions of the vertices of the cutter bit, in the same manner, but the coordinates are given as offsets from its center of rotation, $(L, 0)$. That is, the position of the $j$-th vertex of the cutter bit has the coordinates $(L + x_{cj} , y_{cj} )$.\n\u003c/p\u003e\n\n\u003cp\u003e\nYou may assume $-10000 \\leq x_{wi}, y_{wi}, x_{cj} , y_{cj} \\leq 10000$ for $1 \\leq i \\leq M$ and $1 \\leq j \\leq N$.\n\u003c/p\u003e\n\n\u003cp\u003e\nAll the edges of the workpiece and the cutter bit at initial rotation positions are parallel to the $x$-axis or the $y$-axis. In other words, for each $i$ $(1 \\leq i \\leq M), x_{wi} \u003d x_{wi\u0027}$ or $y_{wi} \u003d y_{wi\u0027}$ holds, where $i\u0027 \u003d (i $ mod$ M) + 1$. Edges are parallel to the $x$- and the $y$-axes alternately. These can also be said about the cutter bit.\n\u003c/p\u003e\n\n\u003cp\u003e\nYou may assume that the cross section of the workpiece forms a simple polygon, that is, no two edges have common points except for adjacent edges. The same can be said about the cutter bit. The workpiece and the cutter bit do not touch or overlap before starting the rotation.\n\u003c/p\u003e\n\n\u003cp\u003e\nNote that $(0, 0)$ is not always inside the workpiece and $(L, 0)$ is not always inside the cutter bit.\n\u003c/p\u003e\n\n\n\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\n\u003cp\u003e\nOutput the number of POI remaining strictly inside the workpiece.\n\u003c/p\u003e\n\n\n\u003ch3\u003eSample Input 1\u003c/h3\u003e\n\n\u003cpre\u003e4 6 5\n-2 5\n-2 -1\n2 -1\n2 5\n-2 1\n-2 0\n0 0\n0 -2\n2 -2\n2 1\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 1\u003c/h3\u003e\n\n\u003cpre\u003e8\u003c/pre\u003e\n\n\n\u003ch3\u003eSample Input 2\u003c/h3\u003e\n\n\u003cpre\u003e14 14 6000\n-3000 3000\n-3000 -3000\n3000 -3000\n3000 -2000\n2000 -2000\n2000 -1000\n1000 -1000\n1000 0\n0 0\n0 1000\n-1000 1000\n-1000 2000\n-2000 2000\n-2000 3000\n3000 3000\n-3000 3000\n-3000 2000\n-2000 2000\n-2000 1000\n-1000 1000\n-1000 0\n0 0\n0 -1000\n1000 -1000\n1000 -2000\n2000 -2000\n2000 -3000\n3000 -3000\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 2\u003c/h3\u003e\n\n\u003cpre\u003e6785772\u003c/pre\u003e\n\n\n\n\u003ch3\u003eSample Input 3\u003c/h3\u003e\n\n\u003cpre\u003e12 12 11\n-50 45\n-50 -45\n40 -45\n40 25\n-10 25\n-10 -5\n0 -5\n0 15\n30 15\n30 -35\n-40 -35\n-40 45\n50 -45\n50 45\n-40 45\n-40 -25\n10 -25\n10 5\n0 5\n0 -15\n-30 -15\n-30 35\n40 35\n40 -45\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 3\u003c/h3\u003e\n\n\u003cpre\u003e966\u003c/pre\u003e\n\n\n\u003ch3\u003eSample Input 4\u003c/h3\u003e\n\n\u003cpre\u003e20 4 11\n-5 5\n-5 -10\n-4 -10\n-4 -1\n-3 -1\n-3 -10\n1 -10\n1 -4\n0 -4\n0 -1\n1 -1\n1 0\n4 0\n4 -1\n10 -1\n10 3\n1 3\n1 4\n10 4\n10 5\n0 0\n3 0\n3 3\n0 3\u003c/pre\u003e\n\n\u003ch3\u003eSample Output 4\u003c/h3\u003e\n\n\u003cpre\u003e64\u003c/pre\u003e\n"}}]}