Max's Anger Contest Series 2 P5 - Job Anger

Points: 12 (partial)

Time limit: 2.0s

Java 5.0s

Python 5.0s

Memory limit: 1G

Author:

maxcruickshanks

Problem types

After landing his first SWE job, Max is assigned to analyze the data lines on a chiplet.

Specifically, the chiplet has $N$ $N$ data lines that are either vertical or horizontal from $(x_{1_{i}}, y_{1_i})$ $(x_{1_{i}}, y_{1_{i}})$ to $(x_{2_i}, y_{2_{i}})$ $(x_{2_{i}}, y_{2_{i}})$ .

It is known that if two data lines intersect, the data travels slower across both lines.

To determine the inefficiency of a chiplet, Max is told to count the number of intersections between vertical and horizontal data lines.

Two data lines intersect if they are in different directions (one is vertical and one is horizontal) and share one point along both lines.

Further, the start point and end point for a data line are never identical.

Since Max is ~~being sabotaged by Wesley~~ new, all of his code produces Runtime Errors, so he asks you to help him as a co-worker.

Can you help Max count the number of intersections of vertical and horizontal data lines?

Constraints

$1 \le N \le 4 \times 10^{5}$ $1 \leq N \leq 4 \times 10^{5}$

$-10^{9} \le x_{1_{i}} \le x_{2_{i}} \le 10^{9}$ $- 10^{9} \leq x_{1_{i}} \leq x_{2_{i}} \leq 10^{9}$

$-10^{9} \le y_{1_{i}} \le y_{2_{i}} \le 10^{9}$ $- 10^{9} \leq y_{1_{i}} \leq y_{2_{i}} \leq 10^{9}$

$x_{1_{i}} \ne x_{2_{i}}$ $x_{1_{i}} \neq x_{2_{i}}$ or $y_{1_{i}} \ne y_{2_{i}}$ $y_{1_{i}} \neq y_{2_{i}}$

Note that both will NOT be true (i.e. a data line cannot be diagonal).

Subtask 1 [20%]

$1 \le N \le 100$ $1 \leq N \leq 100$

$-100 \le x_{1_{i}}, y_{1_{i}}, x_{2_{i}}, y_{2_{i}} \le 100$ $- 100 \leq x_{1_{i}}, y_{1_{i}}, x_{2_{i}}, y_{2_{i}} \leq 100$

Subtask 2 [30%]

$-100 \le x_{1_{i}}, y_{1_{i}}, x_{2_{i}}, y_{2_{i}} \le 100$ $- 100 \leq x_{1_{i}}, y_{1_{i}}, x_{2_{i}}, y_{2_{i}} \leq 100$

Subtask 2 [50%]

No additional constraints.

Input Specification

The first line contains an integer, $N$ $N$ , the number of data lines.

The next $N$ $N$ lines contain four integers, $x_{1_{i}}$ $x_{1_{i}}$ , $y_{1_{i}}$ $y_{1_{i}}$ , $x_{2_{i}}$ $x_{2_{i}}$ , $y_{2_{i}}$ $y_{2_{i}}$ , the start point and end point of the $i^\text{th}$ $i^{th}$ data line.

Output Specification

Output the number of intersections between vertical and horizontal data lines.

Sample Input

Copy

6
0 0 5 0
2 0 9 0
2 0 2 3
2 1 2 5
0 4 3 4
-50 -50 -50 -49

Sample Output

Copy

Explanation for Sample

The first and second data lines intersect with the third data line, and the fourth one intersects with the fifth data line.

Note that, despite the first and second data line overlapping, they do not intersect since they are both horizontal.

Likewise, the third and fourth data line overlap but do not intersect since they are both vertical.

Comments

There are no comments at the moment.