Trải thảm đỏ

View as PDF

Submit solution

Points: 1.29 (partial)
Time limit: 0.38s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
Base on a problem of Alexander Mironenko
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Sảnh đường lớn của khối chuyên Sư Phạm đã được xây dựng để dành cho lễ kỷ niệm ~40~ năm thành lập trường. Nền nhà của sảnh đường có kích thước là ~2000 \times 2000~ mét vuông. Và để lát nền cho sảnh đường người ta cần lát các tấm gạch có kích thước là ~1~ mét vuông. Thật không may là gần đến ngày kỷ niệm trường rồi thì do sơ ý của ~1~ số công nhân đã làm đổ sơn ra nền, làm hỏng mất vẻ đẹp của sảnh đường. Tuy nhiên thật may mắn là vẫn có thể mua thảm cùng màu về để che đi những chỗ bị dính sơn.

Có một điều rất kỳ thú đó là vết sơn đó lại có hình là một cung của hình tròn (có tâm nằm trong phạm vi nền nhà). Bên thi công muốn sửa chữa lỗi lầm bằng cách mua một tấm thảm có dạng là một hình chữ nhật và sau đó trải lên sàn nhà che đi vểt sơn sao cho cạnh của tấm thảm sau khi trải sẽ trùng với các cạnh của các viên gạch (tức là các góc của tấm thảm sẽ phải có toạ độ nguyên). Điều đau đầu của bên thi công giờ là không biết mua tấm thảm với kích thước bao nhiêu thì là có thể lấp được hết vết sơn mà diện tích miếng thảm đó lại là nhỏ nhất. Bạn hãy lập trình giúp bên thi công giải bài toán khó này. Vì bạn là lập trình viên rất giỏi nên bên thi công chỉ cho bạn biết toạ độ của ~2~ điểm đầu mút của cung và của ~1~ điểm nằm trên cung tròn đó mà thôi.

Chú ý bài này nên làm cẩn thận, suy xét hết các trường hợp có thể xảy ra.

Input

  • Dòng ~1~: Số nguyên dương ~T~ là số bộ test ~(1 \leq T \leq 45)~. ~T~ nhóm dòng tiếp theo, mỗi nhóm dòng mô tả ~1~ bộ test, có format như sau:
  • ~2~ dòng đầu, mỗi dòng gồm ~2~ số nguyên là toạ độ của ~2~ điểm đầu mút của vết sơn.
  • Dòng thứ ~3~ gồm ~2~ số nguyên là toạ độ của ~1~ điểm nằm trên vết sơn đó. Biết rằng các toạ độ đều là số nguyên có trị tuyệt đối ~\leq 1000~ và cung tròn nằm trong hình vuông ~[-1000~, ~1000]~ ~\times~ ~[-1000~, ~1000]~.

Output

  • Với mỗi test ghi ra ~1~ số nguyên ~X~ là diện tích nhỏ nhất của miếng thảm.

Sample Input

1
476 612
487 615
478 616

Sample Output

66

Comments

Please read the guidelines before commenting.


There are no comments at the moment.