time limit per test: 0.25 sec. memory limit per test: 65536 KB
input: standard output: standard
Danger! Sudden attack on Russia! These are Americans "again", but this time they are serious. Giant aircraft-carrier "Theodore Roosevelt" is entering the Baltic Sea. At one o'clock American aircraft launched from the carrier bombed Petrozavodsk. At three o'clock we detected the location of "Theodore Roosevelt". In a moment Russian fighters Mig-29 took off into the night air to inflict the crushing strike against the carrier. Using top secret military satellite "Raduga-1" we detected the exact region where the carrier was located - the convex polygon. The fighters launched M rockets and ground forces detected the coordinates of their explosions. You are an indispensable engineer of Russian military forces, and you were waken up by the phone call at four o'clock. They command you to arrive to headquarters for the most important task - detect whether "Theodore Roosevelt" was destroyed or not! You are given all information: the coordinates of vertices of the region polygon and the coordinates of the explosions. It was computed that at least K rockets should have hit the detected region to destroy the carrier. Commander ordered you to complete the work till five o'clock, so you must hurry.
The first line of input contains three integers N, M and K (3<=N<=10^5, 0<=K<=M<=10^5). The following N lines contain coordinates of polygon vertices in counter-clockwise order. And then last M lines contain coordinates of rockets explosions. Is is guaranteed that all coordinates are integer numbers not exceeding 10^9 by their absolute value.
Output "YES" (without quotes) if "Theodore Roosevelt" was destroyed, or "NO" (without quotes) in the other case.
5 4 2 1 -1 1 2 0 4 -1 2 -1 -1 -2 -1 1 -1 0 1 2 3
Dmitry Filippov (DEF)
Petrozavodsk Summer Training Sessions 2004
August 25, 2004
Codeforces (c) Copyright 2010-2021 Mike Mirzayanov