VM 11 Bài 02 - Nối điểm

View as PDF

Submit solution

Points: 1.29 (partial)
Time limit: 2.25s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VNOI Marathon 2011 - Problem Setter: Lê Minh Hoàng
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Trường mầm non SuperKids tổ chức một buổi kiểm tra tư duy hình học của các cháu. Bài kiểm tra như sau: Mỗi bé được phát một tờ giấy trên đó có ~2N~ điểm hoàn toàn phân biệt: ~N~ điểm xanh và ~N~ điểm vàng, các điểm xanh đánh số từ ~1~ tới ~N~ và các điểm vàng cũng được đánh số từ ~1~ tới ~N~. Lần lượt với ~i = 1, 2, \ldots, N~, nếu đoạn thẳng nối từ điểm xanh thứ ~i~ tới điểm vàng thứ ~i~ không có điểm chung với những đoạn thẳng đã nối thì bé phải nối đoạn thẳng đó, ngược lại bé phải thông báo ngay là không nối được ở lượt thứ ~i~ và bài kiểm tra kết thúc, giá trị ~i~ này khi đó được gọi là đáp số của bài kiểm tra. Nếu bé có thể nối được tất cả ~N~ đoạn thẳng thì đáp số quy ước là ~-1~.

Vì số lượng điểm khá lớn nên cô giáo muốn nhanh chóng biết đáp số để chấm bài cho các bé. Hãy giúp các cô giáo của trường SuperKids biết đáp số của bài kiểm tra.

Input

  • Dòng ~1~ chứa số nguyên dương ~N \leq 10^{5}~
  • Dòng tiếp theo, dòng thứ ~i~ chứa ~4~ số nguyên ~x_i, y_i, x'_i, y'_i~ trong đó ~\left(x_{i}, y_{i}\right)~ là tọa độ điểm xanh thứ ~i~ còn ~\left(x'_i, y'_i\right)~ là tọa độ điểm vàng thứ ~i~. Các tọa độ là số nguyên có giá trị tuyệt đối không quá ~10^{9}~.

Output

  • Ghi ra một số nguyên duy nhất là đáp số của bài.

Sample Input

5 
4 5 1 4 
2 1 2 4 
3 3 6 3 
6 2 4 4 
5 1 3 1

Sample Output

4

Comments

Please read the guidelines before commenting.


There are no comments at the moment.