Submission #31756127

Source Code Expand

n = gets.to_i
vertices = Array.new(n) { gets.split.map!(&:to_i) }

m = gets.to_i
offsets = Array.new(m) { gets.split.map!(&:to_i) }

normals = vertices.each_cons(2).map { |(ux, uy), (vx, vy)| [uy - vy, vx - ux] }
normals << (ux, uy = vertices[-1]; vx, vy = vertices[0]; [uy - vy, vx - ux])
bases = normals.map do |dx, dy|
  offsets.max_by { |px, py| dx * px + dy * py }
end
data = normals.zip(bases, vertices).map do |(dx, dy), (bx, by), (px, py)|
  threshold = dx * (bx + px) + dy * (by + py)
  [dx, dy, threshold]
end

#--------#

(q = gets.to_i).times do

px, py = gets.split.map!(&:to_i)

flag = data.all? do |dx, dy, threshold|
  dx * px + dy * py >= threshold
end

puts flag ? :Yes : :No

end

Submission Info

Submission Time
Task G - Intersection of Polygons
User hmmnrst
Language Ruby (2.7.1)
Score 600
Code Size 728 Byte
Status AC
Exec Time 1551 ms
Memory 26944 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 2
AC × 43
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt AC 64 ms 13980 KiB
001.txt AC 552 ms 26456 KiB
002.txt AC 556 ms 26728 KiB
003.txt AC 550 ms 26536 KiB
004.txt AC 543 ms 26660 KiB
005.txt AC 293 ms 13952 KiB
006.txt AC 496 ms 22212 KiB
007.txt AC 267 ms 17956 KiB
008.txt AC 447 ms 15992 KiB
009.txt AC 630 ms 25608 KiB
010.txt AC 428 ms 16004 KiB
011.txt AC 1226 ms 26476 KiB
012.txt AC 1184 ms 26380 KiB
013.txt AC 1180 ms 26612 KiB
014.txt AC 1182 ms 26472 KiB
015.txt AC 1186 ms 26548 KiB
016.txt AC 1185 ms 26528 KiB
017.txt AC 1023 ms 26604 KiB
018.txt AC 1206 ms 26456 KiB
019.txt AC 1151 ms 26488 KiB
020.txt AC 1319 ms 26652 KiB
021.txt AC 1164 ms 26736 KiB
022.txt AC 1133 ms 26788 KiB
023.txt AC 1129 ms 26560 KiB
024.txt AC 1408 ms 26412 KiB
025.txt AC 1086 ms 26636 KiB
026.txt AC 1025 ms 26576 KiB
027.txt AC 920 ms 26472 KiB
028.txt AC 1117 ms 26944 KiB
029.txt AC 1035 ms 26620 KiB
030.txt AC 386 ms 13828 KiB
031.txt AC 1441 ms 26648 KiB
032.txt AC 1484 ms 26560 KiB
033.txt AC 1446 ms 26536 KiB
034.txt AC 1495 ms 26560 KiB
035.txt AC 1510 ms 26532 KiB
036.txt AC 1551 ms 26480 KiB
037.txt AC 1462 ms 26688 KiB
038.txt AC 1461 ms 26572 KiB
039.txt AC 1519 ms 26656 KiB
040.txt AC 1451 ms 26464 KiB
example0.txt AC 58 ms 13996 KiB
example1.txt AC 58 ms 13936 KiB