首页 > ACM题库 > HDU-杭电 > HDU 1633 Orchard Trees-计算几何-[解题报告] C++
2013
12-16

HDU 1633 Orchard Trees-计算几何-[解题报告] C++

Orchard Trees

问题描述 :

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 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.

样例输入:

1.5 1.5  1.5 6.8  6.8 1.5
10.7 6.9  8.5 1.5  14.5 1.5
0 0 0 0 0 0

样例输出:

  15
  17

题目大意:

给出三角形的三个顶点坐标,输出三角形的里面包含多少个整数点(x,y)

由于数据量小,暴力枚举每个顶点到三角形的三个顶点面积和

如果面积和等于三角形的面积,那么此点就在三角形内

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
struct point
{
    double x;
    double y;
};
const int INF=1e9;
const double eps = 1e-9;
double area2(point p1, point p2, point p3);

int main()
{
 
    point p1,p2,p3;
    point p;
    int i,i2;
    int sum;
    while (scanf ("%lf%lf%lf%lf%lf%lf", &p1.x,&p1.y,&p2.x,&p2.y,&p3.x,&p3.y)!=EOF)
    {
        sum=0;
 
        if (p1.x == 0.0 && p1.y == 0.0 && p2.x == 0.0 && p2.y == 0.0 &&
                     p3.x==0.0 && p3.y == 0.0)
            break;
	/*本来这里想做些许优化,从构成三角形的三个点中计算出包含此三角形的最小矩阵,然后再从该小矩阵中枚举所有点,但不知道为何就wa了
	  于是只能枚举所有的点了[0-100][0-100]
        int mix=(int)min(min(p1.x,p2.x),p3.x)-1;
        if(mix<0) mix=0;
        int mx =(int)max(max(p1.x,p2.x),p3.x)+1;
        if(mx>99) mx=99;
        int miy=(int)min(min(p1.y,p2.y),p3.y)-1;
        if(miy<0) miy=0;
        int my =(int)max(max(p1.y,p2.y),p3.y)+1;
        if(my>99) my=99;*/
 
        for (i=1; i<=mx; i++)
            for (i2=1; i2<=my; i2++)
            {
                p.x=i;p.y=i2;
                if ( fabs(area2 (p1,p2,p3) - area2 (p,p1,p2) - area2 (p,p1,p3) - area2 (p,p2,p3))<eps)
                    sum++;
            }
 
        printf ("%4d\n",sum);
 
    }
    return 0;
}
 
 
double area2(point p1, point p2, point p3)
{
    return fabs(p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - p3.x*p2.y - p1.x*p3.y - p2.x*p1.y);
}

解题报告转自:http://blog.csdn.net/criyson/article/details/7458281


  1. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。