USACO 2011 - Nov - Gold - Cow Steeplechase

Xem dạng PDF

Gửi bài giải


Điểm: 0,50 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Người đăng:
Nguồn bài:
http://www.usaco.org/index.php?page=viewproblem2&cpid=93
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Nông dân John vừa có một ý tưởng tuyệt vời về môn thể thao tiếp theo: Bò vượt chướng ngại vật! Như mọi người đã biết, trò chơi vượt chướng ngại vật thường liên quan đến những con ngựa, tại trường đua có rất nhiều chướng ngại vật mà chúng phải nhảy qua. Nông dân John cho rằng cuộc thi tương tự sẽ xảy ra, nếu các chú bò được huấn luyện kĩ lưỡng, cũng như là các chướng ngại vật không quá cao.

Để thiết kế đường đua, John đã vẽ sơ đồ ~N~ chướng ngại vật mà anh ta có thể xây được. Mỗi chướng ngại vật được biểu diễn bởi một đường thẳng trong mặt phẳng ~2D~. Các chướng ngại vật song song với trục tung hoặc trục hoành. Chướng ngại vật thứ ~i~ có các điểm đầu và cuối phân biệt lần lượt là ~(x_{i}, y_{i})~ và ~(u_{i}, v_{i})~. Một ví dụ về sơ đồ:

       --+-------   
    -----+-----
      ---+---     |
         |     |  |
       --+-----+--+-   |
         |     |  |  | |
         |   --+--+--+-+-
               |  |  | |
                  |

Nông dân John muốn xây nhiều chướng ngại vật nhất có thể. Nhưng các chướng ngại vật phải thoả mãn không giao nhau. Với sơ đồ như trên, nông dân John có thể xây dựng được ~7~ chướng ngại vật:

       ----------   
    -----------
      -------     |
               |  |
               |  |    |
               |  |  | |
               |  |  | |
               |  |  | |
                  |

Hai đoạn được gọi là giao nhau nếu chúng có điểm chung, kể cả điểm đầu và cuối. John chắc chắn rằng không có hai chướng ngại vật nào song song với trục tung giao nhau trong dữ liệu input. Tương tự, không có hai chướng ngại vật nào song song với trục hoành giao nhau.

Hãy giúp nông dân John đếm số chướng ngại vật tối đa có thể xây được.

Input

  • Dòng ~1~: số nguyên dương ~N~ ~(1 \le N \le 250)~.
  • Dòng ~2 \dots N + 1~: Dòng thứ ~i + 1~ chứa lần lượt bốn số nguyên dương miêu tả chướng ngại vật thứ ~i~: ~x_{i}, y_{i}, u_{i}, v_{i}~ ~(1 \le x_{i}, y_{i}, u_{i}, v_{i} \le 10^9)~

Output

  • Một dòng duy nhất ghi số chướng ngại vật không giao nhau tối đa có thể xây được.

Sample Input

3
4 5 10 5
6 2 6 12
8 3 8 5

Sample Output

2

Note

  • Có ba chướng ngại vật. Chướng ngại vật thứ nhất song song với trục hoành, có điểm đầu và cuối là ~(4~, ~5)~,~(10~, ~5)~; Chướng ngại vật thứ hai và thứ ba song song với trục tung lần lượt có điểm đầu và cuối là ~(6~, ~2)~,~(6~, ~12)~ và ~(8~, ~3)~,~(8~, ~5)~.
  • Phương án tối ưu là chọn hai chướng ngại vật song song với trục tung.

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.