Sum the indices of up to 100000 points that lie outside a given axis-aligned simple polygon with up to 100000 vertices.
Medium6GeometrySortingNo attempts yetTime limit3sMemory limit256 MBAlice and Bob retired at the age of 40. After more than two decades of work as examples in networking protocol documents, game theory textbooks and several other texts, they were tired. They still wanted to stay active, so they took up gardening.
Alice and Bob planted several vegetable plants in a huge field. Only after they finished did they realize that the plants needed protection from wild animals, so they decided to build a fence around them. The field is the XY plane, and each vegetable plant is a different point in it. A fence is a polygon in the plane. Not every polygon is a valid fence. The fence has to be a single simple polygon with each of its sides parallel to one of the axes. It also has to contain every point that represents a vegetable plant. A fence that runs too close to the plants or to itself makes walking around difficult, so each side of the polygon has to stay away from all plants and from all non-adjacent sides.
Alice and Bob subcontracted the construction of the fence to a nasty multinational. The company kept plenty of lawyers on payroll and no good fence designers, so it failed to comply with all of the requirements. It built a fence that is a simple polygon with sides parallel to the axes, and its sides do stay away from the plants and from itself. The company forgot to make the fence contain all of the plants.
Alice and Bob want to assess the extent of the problem. The plants are not equally valuable to them, so they want to know the total value of the plants that were left outside the fence.
The first line contains two integers P and V, the number of plants and the number of vertices of the polygonal fence (1≤P,V≤105).
Each of the next P lines describes a different plant with two integers Xp and Yp, the coordinates of the plant (−109≤Xp,Yp≤109). The value of the p-th plant in the input is p, for p=1,2,…,P.
Each of the next V lines describes a vertex of the fence with two integers Xv and Yv, the coordinates of the vertex (−109≤Xv,Yv≤109). Vertices are given in counter clockwise order. Each of these points is an actual vertex of the polygon, that is, it is not collinear with its two adjacent vertices. The polygon is a simple polygon with each side parallel to an axis. No two plants are in the same position, and no plant lies on a side of the fence.
Print one line with an integer, the sum of the values of all the plants that lie outside the fence.