Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Inlay Cutters
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 2414Accepted: 1014


The factory cuts rectangular M × N granite plates into pieces using a special machine that is able to perform cuts in 4 different directions: vertically, horizontally, and diagonally at the angle of 45 degrees to the sides of the plate. Every cut is a straight line that starts and ends on the side of the plate.

The factory has been ordered to produce tiles for the inlay, each tile of which is a 45 degrees right triangle. To reduce the time to deliver the tiles it was decided to take all triangles from the already cut plates. Information about all performed cuts is available and your task is to compute the number of triangles of any size that were produced.


The input describes the cuts that were performed on a single rectangular plate. The first line of the input file contains three integer numbers M, N, and K, separated by spaces. M and N (1 ≤ M, N ≤ 50) are the dimensions of the plate, and K (0 ≤ K ≤ 296) is the number of cuts. Next K lines describe the cuts. ith cut is described by four integer numbers Xi,1, Yi,1, Xi,2, and Yi,2, separated by spaces, that represent the starting and ending point of the cut. Both starting (Xi,1, Yi,1) and ending (Xi,2, Yi,2) points of the cut are situated on the plate's border. Both points of the cut are different and the cut goes through the plate. Here, the coordinates by the X axis run from 0 to M, and the coordinates by the Y axis run from 0 to N. All cuts are different.


Write to the output a single integer number - the number of triangles that were produced by the cuts.

Sample Input

7 4 6
6 0 7 1
1 4 1 0
0 4 4 0
0 0 4 4
0 2 7 2
7 0 3 4

Sample Output



[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator