oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

scarecrows Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

scarecrows.html

In JOI village, there is a vast patch of unused land on which N scarecrows stand. Several times a year, the residents of JOI village hold a festival in the barren land, surrounded by the scarecrows. The village chief received a prophecy from the scarecrows and is obliged to build a field on the wastelands to facilitate the festival. In accordance to the prophecy, the village chief has declared that the field must satisfy these conditions:

  • The boundaries of the field are straight lines parallel to the north-south direction or the east-west direction. The field is a rectangle.
  • There are two scarecrows, one at the southwest corner and the other at the northeast corner.
  • There are no other scarecrows within the field.

Of course, you are not allowed to move the precious scarecrows. Given the positions of the N scarecrows, how many ways can a field be built in accordance with the prophecy?

Input

Read from standard input.

  • On the first line, there is one integer N. This means that there are N scarecrows in the wastelands.
  • On the ith line of the next N lines, there are two integers, Xi and Yi. This means that the ith scarecrow is at (Xi, Yi) on the xy plane representing the wastelands. East is in the direction of the positive x-axis and north is in the direction of the positive y-axis.

Output

Print one line containing one integer to standard output, representing the number of ways the field can be built in accordance with the prophecy.

Constraints

All test cases satisfy the following constraints:

  • 1 ≤ N ≤ 200 000.
  • 0 ≤ Xi ≤ 1 000 000 000 (1 ≤ i ≤ N).
  • 0 ≤ Yi ≤ 1 000 000 000 (1 ≤ i ≤ N).
  • Xi (1 ≤ i ≤ N) are all mutually distinct.
  • Yi (1 ≤ i ≤ N) are all mutually distinct.

Subtasks

Subtask 1 (5 points):

  • N ≤ 400 is satisfied.

Subtask 2 (10 points):

  • N ≤ 5 000 is satisfied.

Subtask 3 (85 points):

No further constraints.

Sample Input 1

4
0 0
2 2
3 4
4 3

Sample Output 1

3

Explanation

In this example, there are three ways to build a prophecy-fulfilling field.

  • The rectangle with (0, 0) as the southwest corner and (2, 2) as the northeast corner.
  • The rectangle with (2, 2) as the southwest corner and (3, 4) as the northeast corner.
  • The rectangle with (2, 2) as the southwest corner and (4, 3) as the northeast corner.

Sample Input 2

10
2 1
3 0
6 3
10 2
16 4
0 8
8 12
11 14
14 11
18 10

Sample Output 2

15

Explanation

In this example, the scarecrows' positions are as follows:

scarecrows2.jpg

scarecrows1.jpg

scarecrows.html.bak

Tags

JOI 2013/2014

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
15101.5s256MBMinimum
210121.5s256MBMinimum
385201.5s256MBMinimum
4021.5s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o scarecrows -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.