Birləşmiş qıflar#5043

Birləşmiş qıflar

1 saniyə

64 meqabayt

Çətin

Giflər (gif — sözü çoxluq şəkli) çalaya bənzər obyektlərdir. Gifləri $p_{1}, p_{2}, \dots, p_{n}$ p_1, p_2, \ldots, p_n nöqtələr ardıcıllığı ilə və aşağıdakı xassələri ödəyən ikiölçülü obyektlər kimi müəyyən edək:

- $3 \leq n \leq 1000$ 3 \leq n \leq 1000.

- Əgər $p_{i}$ p_i nöqtəsinin koordinatları $(x_{i}, y_{i})$ (x_i, y_i)-dirsə, $1 < c < n$ 1 < c < n olacaq şəkildə bir $c$ indeks mövcuddur ki, $y_{1} > y_{2} > \dots > y_{c}$ y_1 > y_2 > \ldots > y_c və $y_{c} < y_{c + 1} < y_{c + 2} < \dots < y_{n}$ y_c < y_{c+1} < y_{c+2} < \ldots < y_n. $p_{c}$ p_c nöqtəsinə gifin çıxıntı nöqtəsi deyək.

- Bütün $1 \leq i < c$ 1 \leq i < c üçün $x_{i} < x_{c}$ x_i < x_c və bütün $c < i \leq n$ c < i \leq n üçün $x_{i} > x_{c}$ x_i > x_c.

- $1 < i < c$ 1 < i < c üçün, $p_{i - 1}$ p_{i-1} nöqtəsini $p_{i}$ p_i ətrafında saat əqrəbinin hərəkəti istiqamətində $p_{i}$ p_i və $p_{i + 1}$ p_{i+1} ilə kollinear olması üçün fırlatdıqda yaranan bucaq $180$ dərəcədən böyükdür. Analoji olaraq, $c < i < n$ c < i < n üçün də $p_{i - 1}$ p_{i-1} nöqtəsinin $p_{i}$ p_i ətrafında saat əqrəbinin hərəkəti istiqamətində fırlanması nəticəsində $p_{i}$ p_i və $p_{i + 1}$ p_{i+1} ilə kollinear olması üçün yaranan bucaq $180$ dərəcədən böyükdür.

- Hər iki ardıcıl nöqtəni birləşdirən parçalar yalnız öz uclarında kəsişir.

Məsələn, aşağıdakı şəkildə altı nöqtəli və $c = 4$ c = 4 olan bir gif təsvir edilmişdir:

Gifin $p_{1} p_{2}, p_{2} p_{3}, \dots, p_{n - 1} p_{n}$ p_1p_2, p_2p_3, \ldots, p_{n-1}p_n ardıcıllığına gövde deyirik. Bu məsələdə sizə iki gif $P = (p_{1}, p_{2}, \dots, p_{n})$ P = (p_1, p_2, \ldots, p_n) və $Q = (q_{1}, q_{2}, \dots, q_{m})$ Q = (q_1, q_2, \ldots, q_m) verilir; burada $p_{i}$ p_i nöqtələrinin bütün $x$ koordinatları mənfi tam ədədlər, $q_{i}$ q_i nöqtələrinin isə bütün $x$ koordinatları müsbət tam ədədlərdir.

Təsəvvür edin ki, iki gifin çıxıntı nöqtələri dar bir boru ilə birləşdirilib. Gifləyə su tökülür; su töküldükcə giflər əsas fiziki qanunlara əsasən dolur (hər iki gifdə suyun səviyyəsi eyni olur). Əgər $P$ gifində suyun səviyyəsi $min (y_{1}, y_{n})$ \min(y_1, y_n)-ə çatarsa, su oradan tökülməyə başlayır (eyni hal $Q$ üçün də doğrudur).

Tökmək üçün müəyyən qədər su verilmişdir. İkiölçülü fəzada olduğumuz üçün suyun miqdarı dolmuş sahə ilə ölçülür. Birləşdirici borunun həcmini sıfır qəbul edin.

Giriş

Birinci sətirdə testlərin sayı $t$ verilir. Hər test üç sətrdən ibarətdir. Birinci sətirdə iki gifə tökülmüş suyun miqdarı olan $a$ ( $1 \leq a \leq 100000$ 1 \leq a \leq 100000) tam ədədi verilir. Növbəti iki sətir $P$ və $Q$ giflərini təsvir edir. Hər gif $k$ $x_{1} y_{1} x_{2} y_{2} \dots x_{k} y_{k}$ x_1 y_1 x_2 y_2 \ldots x_k y_k kimi verilir: burada $k$ — gifdəki nöqtələrin ( $P$ üçün $n$ , $Q$ üçün $m$ ) sayıdır, $x_{i}, y_{i}$ x_i, y_i isə nöqtələrin koordinatlarıdır.

Çıxış

$t$ sətir çap edin. Hər bir sətirdə suyun son səviyyəsi olan $L$ — $y$ koordinatında, üç onluq yerədək yuvarlaqlaşdırılmış real ədəd olmalıdır.

Nümunələr

Nümunə 1