说明

\n\n

\r\n\t经过连续若干年的推广，Risk这个游戏已经风靡全国，成为大众喜闻乐见的重要娱乐方式。Risk这个游戏可以理解为一种简易的策略游戏，游戏者的目的是占领所有的土地。由于游戏规则的规定，只要两个国家相邻，就认为两个国家有交战的可能性。我们现在希望知道在当前的局面下，哪些国家之间有交战的可能性。注意，我们认为只有当两个国家的国界线有公共边的时候才认为相邻，若两个国家的领土只有公共点，则认为两个国家不相邻。\r\n

\r\n

\r\n\t每一个国家的边界由一系列线段组成，保证这个边界是一个简单多边形，即严格不自交。为了定位每个国家的位置，我们还给出每个国家最庞大的一支军队的位置，保证这个位置一定出现在某一个形内，而不是出现在某条边界上。\r\n

\r\n

\r\n\t输入输出格式\r\n

\r\n输入格式：
\r\n

\r\n\t
\r\n

\r\n

\r\n\t输入文件的第一行中包括两个整数n,m。分别表示地图上的国家数和描述国家的边界的线段的数量。1<=n<=600，1<=m<=4000。接下来n行，每行用一对数描述了某个国家的主力军队的坐标。接下来m行，每行有4个数x1,y1,x2,y2，（x1,y1）-(x2,y2)描述了一条国界线。所有点的坐标都是0-10000之间的整数。\r\n

\r\n

\r\n\t保证输入的所有线段至多只会在线段交点处相交。整张地图上有且仅有一块面积无限的空白区域不属于任何国家。每一条国界线两侧的区域或者隶属于两个不同的国家，或者分隔了一个国家与那块无穷大的空白区域。即保证一条国界线两侧的区域不同时属于同一个国家或是同时都是空白区域。所有封闭区域内部包含且仅包含一支主力军队，表示了该区域的归属。\r\n

\r\n

\r\n\t

Status	Submit By	Time	Memory	Language	Code	Submit At
AC	Chaser Of Light	162ms	3.8 MiB	C++98	4.7 KiB	2024-7-1 10:59:22
AC	xxw6	246ms	4.9 MiB	C++98	5.7 KiB	2025-3-2 17:47:07
AC	xxw5	448ms	12.2 MiB	C++98	4.4 KiB	2025-5-21 20:59:15

Statistics

Submission Statistics

[ZJOI2008]Risk

Information

Status

Development

Support

Don't have an account?

SIGN IN