This page is still under construction.

Parts of this page are still being built. What you see may change.

Midpoint

Time limit10sMemory limit256 MB

Summary
Count the triples (i, j, k) from three collinear point sets in which C_k is the midpoint of A_i and B_j.
Level

Hard8 of 10

Topics
Geometry, Math, Hash map
Solved
No attempts yet

Problem

You found L+M+NL + M + N points on the coordinate plane and named them A1,…,ALA_1, \dots, A_L, B1,…,BMB_1, \dots, B_M, C1,…,CNC_1, \dots, C_N. Two or more of the points can sit at the same coordinate. The names follow these properties:

  • A1,…,ALA_1, \dots, A_L lie on a single straight line.
  • B1,…,BMB_1, \dots, B_M lie on a single straight line.
  • C1,…,CNC_1, \dots, C_N lie on a single straight line.

Count the triples (i,j,k)(i, j, k) such that CkC_k is the midpoint of AiA_i and BjB_j.

Input

The first line contains three space separated positive integers LL, MM, and NN (1≤L,M,N≤1051 \le L, M, N \le 10^5). The next LL lines describe AA. The ii-th of them contains two space separated integers, the xx coordinate and the yy coordinate of AiA_i. The next MM lines describe B1,…,BMB_1, \dots, B_M in the same format, and the NN lines after that describe C1,…,CNC_1, \dots, C_N. The absolute value of every coordinate is at most 10510^5.

Output

Print the number of triples (i,j,k)(i, j, k) that satisfy the condition.

Examples3

  1. Example 1

    Input
    2 2 3
    0 0
    2 0
    0 0
    0 2
    0 0
    1 1
    1 1
    
    Expected output
    3
    
  2. Example 2

    Input
    4 4 4
    3 5
    0 4
    6 6
    9 7
    8 2
    11 3
    2 0
    5 1
    4 3
    7 4
    10 5
    1 2
    
    Expected output
    8
    
  3. Example 3

    Input
    4 4 4
    0 0
    3 2
    6 4
    9 6
    7 14
    9 10
    10 8
    13 2
    4 2
    5 4
    6 6
    8 10
    
    Expected output
    3