UVa 143 Orchard Trees：数学&计算几何&枚举

UVa 143 Orchard Trees：数学&计算几何&枚举2014-07-22 csdn博客 synapse7143 - Orchard Trees

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&page=show_problem&problem=79

An Orchardist has planted an orchard in a rectangle with trees uniformly spaced in both directions. Thus the trees form a rectangular grid and we can consider the trees to have integer coordinates. The origin of the coordinate system is at the bottom left of the following diagram:

Consider that we now overlay a series of triangles on to this grid. The vertices of the triangle can have any real coordinates in the range 0.0 to 100.0, thus trees can have coordinates in the range 1 to 99. Two possible triangles are shown.

Write a program that will determine how many trees are contained within a given triangle. For the purposes of this problem, you may assume that the trees are of point size, and that any tree （point） lying exactly on the border of a triangle is considered to be in the triangle.

Input and Output

Input will consist of a series of lines. Each line will contain 6 real numbers in the range 0.00 to 100.00 representing the coordinates of a triangle. The entire file will be terminated by a line containing 6 zeroes （0 0 0 0 0 0）.

Output will consist of one line for each triangle, containing the number of trees for that triangle right justified in a field of width 4.

Sample input

1.5 1.51.5 6.86.8 1.510.7 6.98.5 1.514.5 1.50 0 0 0 0 0

Sample output

参考《入门经典》，注意输出要求。

完整代码：

/*0.179s*/#include<cstdio>#include<cmath>#include<algorithm>using namespace std;double area（double x1, double y1, double x2, double y2, double x3, double y3）//三角形有向面积的两倍{return fabs（x1 * y3 + x2 * y1 + x3 * y2 - x2 * y3 - x3 * y1 - x1 * y2）;}int main（void）{double x1, y1, x2, y2, x3, y3;while （scanf（"%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3）, x1 || y1 || x2 || y2 || x3 || y3）{int minx = max（1, （int）ceil（min（x1, min（x2, x3））））;int maxx = min（99, （int）max（x1, max（x2, x3）））;int miny = max（1, （int）ceil（min（y1, min（y2, y3））））;int maxy = min（99, （int）max（y1, max（y2, y3）））;int ans = 0;for （int i = minx; i <= maxx; i++）for （int j = miny; j <= maxy; j++）{double x = （double）i, y = （double）j;if （fabs（area（x1, y1, x2, y2, x, y） + area（x2, y2, x3, y3, x, y） + area（x3, y3, x1, y1, x, y） - area（x1, y1, x2, y2, x3, y3）） < 1e-8） //判断是否在三角形内或边界上ans++;}printf（"%4d
", ans）;}return 0;}