USACO 2011 - Nov - Gold - Cow Steeplechase

View as PDF

Submit solution

Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
http://www.usaco.org/index.php?page=viewproblem2&cpid=93
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.