This page is still under construction.

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

Cow Curling

Time limit1sMemory limit128 MB

Summary
Count the stones of each team that lie inside or on some triangle formed by three opposing stones.
Level

Medium7 of 10

Topics
Geometry, Sorting, Binary search
Solved
No attempts yet

Problem

Cow curling is a popular cold weather sport at the Moolympics.

As in ordinary curling, two teams play against each other, and each team slides NN heavy stones across a sheet of ice (3≤N≤500003 \le N \le 50000). When the match ends, 2N2N stones lie on the ice, and all of them sit at distinct points of the plane.

Scoring works in an unusual way. A stone is captured when it lies inside a triangle whose three corners are stones of the opposing team, and a stone on the boundary of such a triangle counts as captured too. The score of a team is the number of opposing stones that are captured.

Given the positions of all 2N2N stones, compute the final score of the match.

Input

The first line contains the integer NN.

Each of the next NN lines contains two integers, the xx and yy coordinates of a stone of team A.

Each of the following NN lines contains two integers, the xx and yy coordinates of a stone of team B.

Every coordinate is an integer between −40000-40000 and 4000040000, and the 2N2N stones sit at distinct points.

Output

Print the score of team A and the score of team B on one line, separated by a space.

Examples1

  1. Example 1

    Input
    4
    0 0
    0 2
    2 0
    2 2
    1 1
    1 10
    -10 3
    10 3
    
    Expected output
    1 2