Apple Trees

Interview

Time limit1sMemory limit128 MB

Summary

Compute a triangle's area using the shoelace formula and count how many given points lie inside or on its boundary.

Level: Medium4 of 10
Topics: Geometry, Math, Implementation
Solved: No attempts yet

Problem

A farmer bought a triangular plot of land on which N apple trees are planted. Because the boundary of the land is a triangle, it is hard to tell which apple trees belong to the farmer.

Given the coordinates of the three vertices of the triangular plot and the coordinates of the apple trees, write a program that computes the area of the land and the number of apple trees that stand on it.

If an apple tree lies exactly on the boundary of the triangle, it still counts as the farmer's apple tree.

The area of the triangle with vertices (xA, yA), (xB, yB), (xC, yC) can be computed as:

$\frac{|x_A(y_B-y_C)+x_B(y_C-y_A)+x_C(y_A-y_B)|}{2}$

Input

The first three lines contain the coordinates of the triangle's vertices, one per line. The next line contains the number of apple trees N ( $1 \le N \le 100$ ). Each of the following N lines contains the coordinates of one apple tree.

All coordinates are positive integers not greater than 1000, and the two values on each line are separated by a space.

Output

On the first line, print the area of the land to one decimal place. On the second line, print the number of apple trees that stand on the land (including those on the boundary).

Examples3

Example 1
Input
```
1 1
5 1
3 3
4
3 1
3 2
3 3
3 4
```
Expected output
```
4.0
3
```
Example 2
Input
```
3 2
5 4
1 6
3
2 4
3 5
4 3
```
Expected output
```
6.0
3
```

Example 3

Input

Expected output

15.5
2