{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003c/h1\u003e\n\n\u003cp\u003eIn the International City of Pipe Construction, it is planned to repair the water pipe at a certain point in the water pipe network.\nThe network consists of water pipe segments, stop valves and source point.\nA water pipe is represented by a segment on a 2D-plane and intersected pair of water pipe segments are connected at the intersection point.\nA stop valve, which prevents from water flowing into the repairing point while repairing, is represented by a point on some water pipe segment.\nIn the network, just one source point exists and water is supplied to the network from this point.\n\u003c/p\u003e\n\u003cp\u003eOf course, while repairing, we have to stop water supply in some areas, but,\nin order to reduce the risk of riots, the length of water pipes stopping water supply must be minimized.\nWhat you have to do is to write a program to minimize the length of water pipes needed to stop water supply when the coordinates of end points of water pipe segments, stop valves, source point and repairing point are given.\n\u003c/p\u003e\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\n\u003cp\u003eA data set has the following format:\n\u003c/p\u003e\u003cblockquote\u003e\n\u003cvar\u003eN\u003c/var\u003e \u003cvar\u003eM\u003c/var\u003e\u003cbr\u003e\n \u003cvar\u003ex\u003csub\u003es1\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003ey\u003csub\u003es1\u003csub\u003e\u003c/sub\u003e\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003ex\u003csub\u003ed1\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003ey\u003csub\u003ed1\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e\n ...\u003cbr\u003e\n \u003cvar\u003ex\u003csub\u003esN\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003ey\u003csub\u003esN\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003ex\u003csub\u003edN\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003ey\u003csub\u003edN\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e\n \u003cvar\u003ex\u003csub\u003ev1\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003ey\u003csub\u003ev1\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e\n ...\u003cbr\u003e\n \u003cvar\u003ex\u003csub\u003evM\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003ey\u003csub\u003evM\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e\n \u003cvar\u003ex\u003csub\u003eb\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003ey\u003csub\u003eb\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e\n \u003cvar\u003ex\u003csub\u003ec\u003c/sub\u003e\u003c/var\u003e \u003cvar\u003ey\u003csub\u003ec\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e\n\u003c/blockquote\u003e\n\u003cp\u003eThe first line of the input contains two integers, \u003cvar\u003eN\u003c/var\u003e (\u003cvar\u003e1 ≤ N ≤ 300\u003c/var\u003e) and \u003cvar\u003eM\u003c/var\u003e (\u003cvar\u003e0 ≤ M ≤ 1,000\u003c/var\u003e) that indicate the number of water pipe segments and stop valves.\nThe following \u003cvar\u003eN\u003c/var\u003e lines describe the end points of water pipe segments.\nThe \u003cvar\u003ei\u003c/var\u003e-th line contains four integers, \u003cvar\u003ex\u003csub\u003esi\u003c/sub\u003e\u003c/var\u003e, \u003cvar\u003ey\u003csub\u003esi\u003c/sub\u003e\u003c/var\u003e, \u003cvar\u003ex\u003csub\u003edi\u003c/sub\u003e\u003c/var\u003e and \u003cvar\u003ey\u003csub\u003edi\u003c/sub\u003e\u003c/var\u003e that indicate the pair of coordinates of end points of \u003cvar\u003ei\u003c/var\u003e-th water pipe segment.\nThe following \u003cvar\u003eM\u003c/var\u003e lines describe the points of stop valves.\nThe \u003cvar\u003ei\u003c/var\u003e-th line contains two integers, \u003cvar\u003ex\u003csub\u003evi\u003c/sub\u003e\u003c/var\u003e and \u003cvar\u003ey\u003csub\u003evi\u003c/sub\u003e\u003c/var\u003e that indicate the coordinate of end points of \u003cvar\u003ei\u003c/var\u003e-th stop valve.\nThe following line contains two integers, \u003cvar\u003ex\u003csub\u003eb\u003c/sub\u003e\u003c/var\u003e and \u003cvar\u003ey\u003csub\u003eb\u003c/sub\u003e\u003c/var\u003e that indicate the coordinate of the source point.\nThe last line contains two integers, \u003cvar\u003ex\u003csub\u003ec\u003c/sub\u003e\u003c/var\u003e and \u003cvar\u003ey\u003csub\u003ec\u003c/sub\u003e\u003c/var\u003e that indicate the coordinate of the repairing point.\n\u003c/p\u003e\n\u003cp\u003eYou may assume that any absolute values of coordinate integers are less than 1,000 (inclusive.) \nYou may also assume each of the stop valves, the source point and the repairing point is always on one of water pipe segments and that that each pair among the stop valves, the source point and the repairing point are different.\nAnd, there is not more than one intersection between each pair of water pipe segments.\nFinally, the water pipe network is connected, that is, all the water pipes are received water supply initially.\n\u003c/p\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\u003cp\u003ePrint the minimal length of water pipes needed to stop water supply in a line.\nThe absolute or relative error should be less than or \u003cvar\u003e10\u003csup\u003e-6\u003c/sup\u003e\u003c/var\u003e.\nWhen you cannot stop water supply to the repairing point even though you close all stop valves, print \"\u003ccode\u003e-1\u003c/code\u003e\" in a line.\n\u003c/p\u003e\n\n\u003ch2\u003eSample Input 1\u003c/h2\u003e\n\n\u003cpre\u003e1 2\n0 0 10 0\n1 0\n9 0\n0 0\n5 0\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 1\u003c/h2\u003e\n\n\u003cpre\u003e9.0\n\u003c/pre\u003e\n\n\u003ch2\u003eSample Input 2\u003c/h2\u003e\n\n\u003cpre\u003e5 3\n0 4 2 4\n0 2 2 2\n0 0 2 0\n0 0 0 4\n2 0 2 4\n0 2\n1 0\n2 2\n1 4\n2 1\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 2\u003c/h2\u003e\n\n\u003cpre\u003e3.0\n\u003c/pre\u003e\n\n\n\u003ch2\u003eSample Input 3\u003c/h2\u003e\n\n\u003cpre\u003e2 1\n0 0 0 4\n0 2 2 2\n1 2\n0 1\n0 3\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 3\u003c/h2\u003e\n\n\u003cpre\u003e-1\n\u003c/pre\u003e\n"}}]}