29ος ΠΔΠ Καμπ (κοινά)
Η ληστεία των ρομπότ (robots)

Βρισκόμαστε στο μέλλον και τα ρομπότ έχουν κυριαρχήσει τον κόσμο! Για καλή σας τύχη, ως πολύ καλοί προγραμματιστές, έχετε την ικανότητα να δαμάζετε τα ρομπότ και να τα αναγκάζετε να υπακούσουν στις επιθυμίες σας. Σκέφτεστε λοιπόν ότι μπορείτε να χρησιμοποιήσετε τα ρομπότ προς όφελός σας. Κατοικείτε στη χώρα των αλγορίθμων που ο χάρτης της είναι ένα τετράγωνο πλέγμα άπειρης έκτασης. Πάνω στο πλέγμα βρίσκονται \(C\) τράπεζες τις οποίες έχετε σκοπό να ληστέψετε. Γι’ αυτό τον σκοπό θα χρησιμοποιήσετε τα ρομπότ, τα οποία θα βάλετε να κάνουν τις ληστείες για σας.

Το σχέδιό σας έχει ως εξής. Αρχικά θα εξαπολύσετε τα ρομπότ από το σπίτι σας, που βρίσκεται στο σημείο με συντεταγμένες \((0, 0)\). Τα ρομπότ θα περάσουν και θα ληστέψουν όλες τις τράπεζες και θα συναντηθούν όλα μαζί στο κρησφύγετό σας, που βρίσκεται στο σημείο με συντεταγμένες \((10^6, 10^6)\), όπου θα πάτε κι εσείς έπειτα για να πάρετε τα λεφτά. Ωστόσο, έχετε σαν απαίτηση τα ρομπότ να κινούνται μόνο με βήματα είτε προς τα πάνω, είτε προς τα δεξιά (δηλαδή καμία συντεταγμένη τους δεν μπορεί να μειώνεται), ώστε να μην μπορέσουν να γυρίσουν πίσω και προδώσουν τον τόπο διαμονής σας. Επιπλέον, φοβάστε πως αν χρησιμοποιήσετε πολλά ρομπότ, αυτά μπορεί να εξεγερθούν και να ζητήσουν μερίδιο των χρημάτων, συνεπώς θα θέλατε να χρησιμοποιήσετε όσο γίνεται λιγότερα, ώστε το σχέδιό σας να είναι εφικτό δεδομένων των περιορισμών.

Γράψτε ένα πρόγραμμα όπου να δέχεται ως είσοδο τις τοποθεσίες των \(C\) τραπεζών και να υπολογίζει το ελάχιστο πλήθος ρομπότ που απαιτείται προκειμένου να πραγματοποιηθεί η ληστεία.

Δεδομένα εισόδου (robots.in)

Η πρώτη γραμμή της εισόδου θα περιέχει έναν φυσικό αριθμό \(C\), το πλήθος των τραπεζών. Οι επόμενες \(C\) γραμμές θα περιέχουν τις συντεταγμένες των τραπεζών πάνω στο επίπεδο. Συγκεκριμένα, ή \(i\)-οστή γραμμή θα περιέχει το ζεύγος \((x_i, y_i)\) που δηλώνει ότι η \(i\)-οστή τράπεζα βρίσκεται στο σημείο με τις αντίστοιχες συντεταγμένες εντός του επιπέδου.

Δεδομένα εξόδου (robots.out)

Η έξοδος πρέπει να περιέχει μία γραμμή με ακριβώς έναν φυσικό αριθμό: τον ελάχιστο αριθμό ρομπότ που απαιτούνται για να ληστέψουμε όλες τις τράπεζες.

Παράδειγμα αρχείων εισόδου - εξόδου

robots.in	robots.out
3 1 7 3 5 1 4	2

Εξήγηση: Υπάρχουν συνολικά τρεις τράπεζες στα σημεία \((1, 4)\), \((1, 7)\) και \((3, 5)\). Θα χρειαστούμε αναγκαστικά \(2\) ρομπότ. Το πρώτο θα ξεκινήσει από την αρχή \((0, 0)\) και θα ληστέψει τις τράπεζες στα σημεία \((1, 4)\) και \((3, 5)\). Το δεύτερο θα ξεκινήσει επίσης από την αρχή και θα ληστέψει την τράπεζα στο σημείο \((1, 7)\). Εξίσου καλά θα μπορούσε να ληστέψει το πρώτο την τράπεζα στο σημείο \((3, 5)\) και το δεύτερο τις τράπεζες στα σημεία \((1, 4)\) και \((1, 7)\). Ένα μόνο ρομπότ, κινούμενο μόνο δεξιά και πάνω, δεν μπορεί να περάσει και από τις τρεις τράπεζες για να τις ληστέψει.

Περιορισμοί

Οι συντεταγμένες θα κυμαίνονται από \(0\) μέχρι \(10^6 = 1.000.000\).
Όριο χρόνου εκτέλεσης: \(1\) sec.
Όριο μνήμης: \(64\) MB.

Υποπροβλήματα