#P5545. Super Ray Attack

    ID: 18775 Type: Default 1000ms 256MiB

Super Ray Attack

Super Ray Attack

The map is a two-dimensional plane. All of JYY's territory is located below the \(x\)‐axis, while all enemies are located above the \(x\)‐axis.

Inside JYY's territory, there are \(T\) laser towers and \(S\) energy sources. The coordinate of the \(i\)-th laser tower \(T_i\) is \((tx_i, ty_i)\) and that of the \(i\)-th source \(S_i\) is \((sx_i, sy_i)\). There are \(D\) enemies with the coordinate of the \(i\)-th enemy \(D_i\) being \((dx_i, dy_i)\).

Any two laser towers can be connected to form an energy wall. When an energy source emits energy toward an enemy, if the line segment connecting the source and the enemy intersects an energy wall, the energy is greatly enhanced to form a super ray that instantly eliminates the enemy.

A valid super ray attack is represented by a quadruple \(\{T_i, T_j, S_k, D_l\}\) satisfying: \[ 1 \le i < j \le T, \quad 1 \le k \le S, \quad 1 \le l \le D, \] such that the line segment \(T_iT_j\) and the line segment \(S_kD_l\) intersect. The game guarantees that among these \(T+S+D\) points there are no duplicate points and no three points are collinear.

Your task is to calculate the total number of valid super ray attacks.

Note: Two line segments \(p_1p_2\) and \(p_3p_4\) intersect if and only if \[ \text{orient}(p_1,p_2,p_3) \times \text{orient}(p_1,p_2,p_4) < 0 \quad \text{and} \quad \text{orient}(p_3,p_4,p_1) \times \text{orient}(p_3,p_4,p_2)

inputFormat

The first line contains three integers \(T\), \(S\), and \(D\) representing the number of laser towers, energy sources, and enemies respectively.

The next \(T\) lines each contain two space-separated integers \(tx_i\) and \(ty_i\), the coordinates of the \(i\)-th laser tower.

The following \(S\) lines each contain two space-separated integers \(sx_i\) and \(sy_i\), the coordinates of the \(i\)-th energy source.

The last \(D\) lines each contain two space-separated integers \(dx_i\) and \(dy_i\), the coordinates of the \(i\)-th enemy.

It is guaranteed that all towers and sources lie below the \(x\)-axis and all enemies lie above the \(x\)-axis. No three points are collinear.

outputFormat

Output a single integer representing the total number of valid super ray attack schemes.

sample

2 1 1
-3 -4
3 -4
0 -5
0 5
1