CARPET - Trải thảm đỏ
Giới hạn- Thời gian: 0.1s
- Bộ nhớ: 1536MB
- Mã nguồn: 20000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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*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 ≤ T ≤ 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 ≤ 1000 và cung tròn nằm trong hình vuông [-1000,1000] * [-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 .
Example
Input: 1 476 612 487 615 478 616 Output: 66
- Người up: hard7771988
- Nguồn bài: Base on a problem of Alexander Mironenko