COCI-20 (2020) - Γύρος #6 - 4 ( Geometrija)

View as PDF

Submit solution

Points: 40 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python
Geometrija

Σας δίνονται n σημεία στο επίπεδο, έτσι ώστε τρία σημεία να μη μπορούν να βρεθούν στην ίδια ευθεία.

Λέμε ότι τα ευθύγραμμα τμήματα \overline{AB} και \overline{CD} διασταυρώνονται αν έχουν ένα κοινό σημείο X, διαφορετικό από τα σημεία A, B, C και D.

Έστω S το σύνολο όλων των ευθύγραμμων τμημάτων μεταξύ των ζευγών των δεδομένων σημείων. Βρείτε τον αριθμό των τμημάτων του S που δεν διασταυρώνονται με κανένα άλλο τμήμα στο S.

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο n\;(3 \le n \le 1000), τον αριθμό των σημείων.

Οι ακόλουθες n γραμμές περιέχουν ακέραιους αριθμούς x_i και y_i\;(-10^9 \le x_i, y_i \le 10^9), τις συντεταγμένες των σημείων.

Έξοδος

Μία γραμμή με τον αριθμό των τμημάτων του S που δεν διασταυρώνονται με κανένα άλλο τμήμα στο S.

Βαθμολογία
 Υποπρόβλημα    Βαθμοί   Περιορισμοί
1 20 3 \le n \le 40
2 30 3 \le n \le 200
3 60 Κανένας επιπλέον περιορισμός.


Παραδείγματα

input

4
1 1
-1 1
-1 -1
1 -1

output

4

input

4
-1 -1
1 -1
0 1
0 0

output

6
Επεξήγηση παραδειγμάτων:

coci20f4-figure.svg


Comments

There are no comments at the moment.