Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PVOI14_1 - ĐINH GHIM

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/pvoi14_1


Sau hàng chục năm giảng dạy, thầy Minh đã sưu tập được rất nhiều bài tập tin học và giờ đây thầy muốn tổng hợp và phân loại chúng. Các bài tập được in trong N tờ giấy đặt trên bàn làm việc và thầy Minh muốn ghim các tờ giấy xuống dưới mặt bàn bằng một đinh ghim duy nhất (việc này là cần thiết nhằm tránh cho chúng bị xê dịch hoặc bị gió thổi bay).

Mặt bàn có thể coi như mặt phẳng với hệ tọa độ Descartes vuông góc Ο. Vị trí của các tờ giấy được xác định bởi  hình chữ nhật đánh số từ 1 tới . Mỗi cạnh của mỗi hình chữ nhật song song hoặc vuông góc với đường phân giác của góc phần tư thứ nhất (góc ). Đinh ghim phải đặt ở vị trí là điểm có hoành độ và tung độ đều là số nguyên, đồng thời điểm đó phải thuộc miền trong của tất cả các hình chữ nhật (không tính đường biên).

Mặt bàn có thể coi như mặt phẳng với hệ tọa độ Descartes vuông góc Οxy. Vị trí của các tờ giấy được xác định bởi N hình chữ nhật đánh số từ 1 tới N. Mỗi cạnh của mỗi hình chữ nhật song song hoặc vuông góc với đường phân giác của góc phần tư thứ nhất (góc xOy). Đinh ghim phải đặt ở vị trí là điểm có hoành độ và tung độ đều là số nguyên, đồng thời điểm đó phải thuộc miền trong của tất cả các hình chữ nhật (không tính đường biên).

Yêu cầu: Hãy giúp thầy Minh đếm số vị trí có thể đặt đinh ghim.

Input

  • Dòng 1 chứa số nguyên dương N (N ≤ 105).
  • N dòng tiếp theo, mỗi dòng chứa 8 số nguyên xA, yA, xB, yB, xC, yC, xD, yD cách nhau bởi dấu cách là tọa độ 4 đỉnh (xA, yA), (xB, yB), (xC, yC), (xD, yD) của một tờ giấy theo đúng thứ tự xác định hình chữ nhật tương ứng. Các tọa độ là số nguyên có giá trị tuyệt đối không quá 109.
  • 40% số điểm tương ứng với các test có N ≤ 100 và các tọa độ có giá trị tuyệt đối không quá 100.

Output

Ghi ra một số nguyên duy nhất là số vị trí có thể đặt đinh ghim.

Example

Input:
3
3 0 0 3 4 7 7 4 
5 0 7 2 2 7 0 5 
5 7 7 5 3 1 1 3

Output:
4

Được gửi lên bởi:VOJ Team
Ngày:2014-12-15
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:PreVOI 2014

hide comments
2021-05-27 18:03:24
Tham khảo: https://vnspoj.github.io/problems/PVOI14_1
2019-08-03 12:40:51
Chuyển tọa độ về 2 đường chéo chính và phụ rồi dùng công thức giao hình chữ nhật, sau đó tìm cách tính số cách đặt <(")
2017-10-02 19:25:19
Bài này làm như nào vậy ace
2016-10-20 14:36:38
trâu cũng AC :v

Last edit: 2016-10-20 14:37:49
2014-12-21 17:30:28 [ND] HI
Chú ý INT64 hay LONG LONG nhá anh em :v
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.