JOI Poster
Time limit2sMemory limit512 MB
Count ordered quadruples of stars A, B, C, D where the circle centered at A through B lies inside the poster and strictly contains the circle centered at C through D.
- Level
Medium7 of 10
- Topics
- Geometry, Brute force, Math, Implementation
- Solved
- No attempts yet
Problem
Director K is designing three posters to support the Japanese team at the International Olympiad in Informatics. Each poster will feature one of the letters J, O, and I. Having already finished the posters for the letters J and I, Director K decides to design the remaining poster for the letter O with the night sky of Australia as its background.
The poster is a rectangle of width W and height H, with its lower-left corner at coordinates (0, 0) and its upper-right corner at (W, H). N stars are printed on the poster. The coordinates of the i-th star Si (1 ≤ i ≤ N) on the poster are (Xi, Yi), and no two stars share the same coordinates.
While creating the design for the letter O, Director K thought as follows. Choose four distinct stars from the N stars and call them A, B, C, and D. Let circle O1 be the circle centered at A that passes through B, and let circle O2 be the circle centered at C that passes through D. The four stars A, B, C, D are candidates for Director K's design when the two circles O1 and O2 satisfy both of the following conditions.
- Circle O1 contains circle O2 in its interior. That is, every point inside or on the circumference of circle O2 lies in the interior of circle O1 (the circumference is excluded).
- Neither circle extends outside the rectangular region of the poster. That is, for every point (X, Y) inside or on the circumference of the circle, 0 ≤ X ≤ W and 0 ≤ Y ≤ H.
How many ways are there to choose four stars A, B, C, D that are candidates for Director K's design?
Given the size of the poster and the information about the stars, write a program that determines how many ways there are to choose four stars A, B, C, D that are candidates for Director K's design.
Input
Read the following input from standard input.
- The first line contains the integers N, W, H separated by spaces, representing the number of stars printed on the poster and the width and height of the poster, respectively.
- The i-th of the following N lines (1 ≤ i ≤ N) contains two integers Xi, Yi (0 ≤ Xi ≤ W and 0 ≤ Yi ≤ H) separated by a space, representing the coordinates of star Si on the poster.
Output
Print a single line to standard output containing an integer that represents how many ways there are to choose four stars A, B, C, D that are candidates for Director K's design.
Constraints
- 4 ≤ N ≤ 50.
- 1 ≤ W ≤ 1 000.
- 1 ≤ H ≤ 1 000.
- 0 ≤ Xi ≤ W.
- 0 ≤ Yi ≤ H.
- No two stars share the same coordinates.