ĐINH GHIM

View as PDF

Submit solution

Points: 0.59 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
PreVOI 2014
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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~ ~\leq~ ~10^{5}~ ).
  • N dòng tiếp theo, mỗi dòng chứa 8 số nguyên ~x_{A}~ , ~y_{A}~ , ~x_{B}~ , ~y_{B}~ , ~x_{C}~ , ~y_{C}~ , ~x_{D}~ , ~y_{D}~ cách nhau bởi dấu cách là tọa độ 4 đỉnh ( ~x_{A}~ , ~y_{A}~ ), ( ~x_{B}~ , ~y_{B}~ ), ( ~x_{C}~ , ~y_{C}~ ), ( ~x_{D}~ , ~y_{D}~ ) 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á ~10^{9}~ .
  • 40% số điểm tương ứng với các test có ~N \leq 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.

Sample 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

Sample Output

4

Comments

Please read the guidelines before commenting.


There are no comments at the moment.