#P1899. Farmer Bill's Problem
Farmer Bill's Problem
据传闻,地球时常有不明飞行物(UFO)造访。有时UFO着陆后会留下烧焦区域,观察显示这些区域呈圆形。
最近,农民比尔在他那片规整的矩形麦田里发现了这样的圆形区域。比尔对所有神秘事物都极为喜爱,因此决定将麦田里的这些圆形区域保留下来。不过,尽管他是一名UFO研究者,但比尔首先是个农民,他需要收割小麦。于是他打算保留一些包含圆形的矩形区域,这些矩形既不接触也不重叠,且其边与麦田的边平行,而所有UFO留下的圆形必须完全处于这些矩形内部。为了能收割尽可能多的麦田,保留区域的总面积需尽可能小。
现在比尔想知道他能够收割的麦田面积,快来帮帮他吧!
输入的第一行包含两个整数和(),表示比尔麦田的尺寸。假设比尔的麦田在平面上的位置使得其四个角的坐标分别为、、和。输入的第二行是(),表示比尔麦田里UFO留下的圆形数量。接下来的行每行描述一个圆形,包含三个正整数、和,分别表示圆心坐标和半径。这些圆形可能相切、重叠或者相互包含,但全都完全位于麦田边界之内。
输出一个整数,即比尔能够收割的麦田部分的面积。
输出
输出一个整数,表示比尔能够收割的麦田部分的面积。
输入数据
10 8
2
3 3 1
1 1 1
输出数据
64