trang chủ / đề bài / icpc23_mb_k

Bullethell

Đề bài

Mô tả

Trên đường tới Dinh thự Quỷ Đỏ (Scarlet Devil Mansion), bạn gặp Patchouli Knowledge, người sẽ tìm cách ngăn bạn tiến lên.

Để tránh làm hư hại dinh thự, Patchouli phủ lên dinh thự một phép thuật thao túng không gian, tạm thời xóa bỏ các bức tường và biến sàn nhà thành một mặt phẳng hai chiều vô hạn.

Ngay sau đó, cô ấy dùng phép thao túng nước khiến bạn bị đóng băng và trượt trên sàn theo hướng của vectơ (xt,yt) với tốc độ v đơn vị độ dài mỗi giây. Nói cách khác, nếu lúc bị đóng băng (thời điểm 0) bạn ở điểm (x0,y0), thì tại thời điểm k≥0 (một số thực bất kỳ) bạn ở điểm

(x0,y0)+k·vxt2+yt2·(xt,yt).

Cuối cùng, cô ấy tung ra q phép thao túng gỗ. Phép thứ i được mô tả bởi ba điểm Oi,Ai,Bi, thời điểm bắt đầu li và thời điểm kết thúc ri.

Trong phép thứ i, cô ấy triệu hồi một cành cây dài vô hạn với độ dày 10−100 nằm dọc theo tia OiAi. Sau đó cô ấy quét cành cây theo chiều kim đồng hồ cho tới khi nó chạm tia OiBi, rồi quét ngược chiều kim đồng hồ cho tới khi nó trở về tia OiAi. Cô ấy bắt đầu quét qua lại từ thời điểm li và kết thúc ở thời điểm ri. Sau đòn tấn công, cành cây biến mất hoàn toàn.

Bạn bị phép thứ i đánh trúng tại thời điểm k nếu li≤k≤ri và vị trí của bạn tại thời điểm k nằm trong vùng quét của phép thứ i (không quan trọng cành cây đang ở đâu vì cô ấy quét với tốc độ ánh sáng!). Vùng quét là phần mặt phẳng mà cành cây quét qua khi quay theo chiều kim đồng hồ từ tia OiAi tới tia OiBi, tính cả hai tia biên.

Bạn sẽ ngất nếu bị đánh trúng (bởi ít nhất một phép) liên tục trong T giây, tức là có một đoạn thời gian độ dài T mà tại mọi thời điểm trong đoạn đó bạn đều bị ít nhất một phép đánh trúng.

Biết vị trí của bạn khi bị đóng băng là (x0,y0), hãy xác định bạn có sống sót qua các phép thuật của Patchouli hay không.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test. Dòng đầu tiên chứa số bộ test t (1≤t≤100). Tiếp theo là mô tả các bộ test.

  • Dòng đầu tiên của mỗi bộ test chứa 6 số nguyên x0,y0,xt,yt,v,T (|xt|+|yt|>0, 1≤v,T≤109): tọa độ vị trí ban đầu, vectơ chuyển động, tốc độ trượt và thời gian cần thiết để bạn ngất.
  • Dòng tiếp theo chứa một số nguyên q (1≤q≤2×105): số phép thao túng gỗ mà Patchouli sử dụng.
  • Dòng thứ i trong q dòng tiếp theo chứa 8 số nguyên xOi,yOi,xAi,yAi,xBi,yBi,li,ri (0≤li<ri≤109): tọa độ các điểm Oi,Ai,Bi và thời điểm bắt đầu, kết thúc của phép thứ i. Dữ liệu đảm bảo Oi,Ai,Bi không thẳng hàng.

Dữ liệu đảm bảo mọi tọa độ (x,y) trong dữ liệu vào thỏa mãn |x|,|y|≤109 và tổng các q không vượt quá 2×105.

Dữ liệu ra

Với mỗi bộ test, in ra "GIT GUD" nếu bạn sống sót, ngược lại in ra "FAINTED".

Ràng buộc

  • 1≤t≤100
  • |xt|+|yt|>0, 1≤v,T≤109
  • 1≤q≤2×105, tổng các q không vượt quá 2×105
  • 0≤li<ri≤109
  • Mọi tọa độ có giá trị tuyệt đối không vượt quá 109; Oi,Ai,Bi không thẳng hàng.

Ví dụ

Input Output Giải thích
3
0 1 1 0 1 2
1
2 2 4 0 0 0 1 10
0 1 1 0 1 3
1
2 2 4 0 0 0 1 10
0 1 1 0 1 3
2
2 2 4 0 0 0 1 10
2 2 6 0 4 0 1 10
FAINTED
GIT GUD
FAINTED
Tại thời điểm k bạn ở điểm (k,1). Vùng quét của phép (O,A,B)=((2,2),(4,0),(0,0)) là góc vuông hướng xuống dưới tại (2,2), chứa điểm (k,1) khi 1≤k≤3. Bộ test thứ nhất và thứ hai: bạn bị đánh trúng từ giây 1 tới giây 3 (đủ 2 giây nhưng không đủ 3 giây). Bộ test thứ ba: phép thứ nhất đánh trúng từ giây 1 tới giây 3, phép thứ hai (vùng quét giữa hai tia hướng tới (6,0) và (4,0)) đánh trúng từ giây 3 tới giây 4, tổng cộng 3 giây liên tục.
2
0 0 3 4 5 3
2
10 0 3 4 6 8 0 10
10 0 6 8 12 16 0 10
0 0 3 4 5 3
2
10 0 3 4 6 8 0 10
10 0 6 8 12 16 3 10
FAINTED
GIT GUD
Vectơ (3,4) có độ dài 5 và v=5, nên tại thời điểm k bạn ở điểm (3k,4k). Phép thứ nhất (đỉnh (10,0), quét từ tia hướng tới (3,4) sang tia hướng tới (6,8)) đánh trúng khi 1≤k≤2, phép thứ hai đánh trúng khi 2≤k≤4: tổng cộng 3 giây liên tục. Ở bộ test thứ hai, phép thứ hai chỉ bắt đầu từ giây 3, nên chỉ có hai đoạn [1,2] và [3,4], mỗi đoạn dài 1 giây.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0