This page is still under construction.

Parts of this page are still being built. What you see may change.

Mystery Sign

Time limit2sMemory limit512 MB

Summary
Given convex polygon A, convex polygon B inside it, and a polyline of K points, decide whether every sign point lies strictly inside A and strictly outside B, or count the violating points.
Level

Medium6 of 10

Topics
Geometry, Binary search, Implementation, Brute force
Solved
No attempts yet

Problem

After a long job search, Taeyoung lands a job. With the job market shrinking for many reasons, he is delighted at this job, welcome as rain in a drought. But nothing is certain until it is signed, so Taeyoung loses sleep, eager to write the employment contract as soon as possible.

In this contactless era brought on by social distancing, Taeyoung writes the employment contract through the remote electronic signing service MODUSIGN. After receiving the email, his anxiety disappears, and he begins a happy deliberation over how to make a cool sign on the first contract he has ever filled out.

Taeyoung wants a sign that stands out neither too much nor too little, with a distinctive feel. Having always shown a keen geometric sense, he intends to make the sign by following rules of his own. The rules he sets are as follows.

  • Taeyoung chooses two convex polygons A and B.
  • Polygon B lies entirely inside A.
  • Taeyoung's sign is a polyline that connects several points in order.
  • The points making up Taeyoung's sign must lie inside A. They must also lie outside B.
  • No point of the sign lies on the boundary of either shape.
  • All coordinates given in the problem are integers.

Given information about the two shapes A and B and about the polyline Taeyoung signed, write a program that decides whether the sign satisfies the given rules. If Taeyoung's sign violates the rules, count how many points violate them.

Input

The first line gives three natural numbers N, M, K separated by spaces.

  • N is the number of points making up shape A. (3 ≤ N ≤ 10,000)
  • M is the number of points making up shape B. (3 ≤ M ≤ 10,000)
  • K is the number of points making up Taeyoung's sign. (2 ≤ K ≤ 300,000)

The second line gives the coordinates of the N points making up shape A as 2N integers separated by spaces. Each point's coordinates are given in the form X Y separated by a space. The points are given in counterclockwise order.

The third line gives the coordinates of the M points making up shape B as 2M integers separated by spaces. Each point's coordinates are given in the form X Y separated by a space. The points are given in counterclockwise order.

  • Every point of polygon B lies inside polygon A, not on its boundary.

The fourth line gives the coordinates of the K points making up the sign as 2K integers separated by spaces. Each point's coordinates are given in the form X Y separated by a space. Connecting the points in order completes Taeyoung's sign.

  • All coordinates are integers. (-1,000,000,000 ≤ X, Y ≤ 1,000,000,000)
  • No point given in the problem is repeated.
  • No point of the sign lies on the boundary of shape A or B.

Output

If the given sign satisfies Taeyoung's rules, print "YES".

If it does not satisfy the rules, print the number of points that violate the conditions as an integer.

Examples3

  1. Example 1

    Input
    8 5 8
2 5 1 6 -2 6 -4 5 -5 2 -1 0 2 1 3 3
0 5 -4 4 -2 1 1 1 2 3
-4 2 -3 5 -3 2 1 5 2 2 -2 5 -1 5 2 4
    Expected output
    YES

  2. Example 2

    Input
    8 5 9
2 5 1 6 -2 6 -4 5 -5 2 -1 0 2 1 3 3
0 5 -4 4 -2 1 1 1 2 3
-4 2 -3 6 -3 2 2 2 1 3 -2 4 1 5 0 7 -2 5
    Expected output
    4

  3. Example 3

    Input
    3 3 3
-1 -1 4 -1 -1 4
0 0 1 0 0 1
-2 -2 2 0 0 2
    Expected output
    1