下图是刘汝佳编著的《算法竞赛入门经典》一书第2部分第5章5.4.3果园里的树的题目描述
我做这道题的时候借鉴了书中【分析】的计算三角形有向面积的函数，不过书中写的解题方法应该是存在问题的。其认为此题需要计算如下等式
只有当这个等式成立时才说明O点在△ABC中。其实正是因为其给出的函数是可以根据输入的三个点的顺序是顺时针序还是逆时针序来计算有向面积，而有向面积在顶点为逆时针输入时为正，顺时针输入时为负，，所以给定三角形区域外的O点也可以使等式成立。我给出的算法是判断△OAB,△OBC,△OCA的三个顶点按逆时针输入时有向面积若都为正，则表示O点在△ABC中，否则不在。以下是我的算法实现。
#include <stdio.h>#include <math.h>typedef struct { double x, y; }Point;double area2(Point a, Point b, Point c){return a.x*b.y+c.x*a.y+b.x*c.y-c.x*b.y-a.x*c.y-b.x*a.y;}int main(){Point t[3], a, b, c;while(scanf("%lf %lf %lf %lf %lf %lf", &t[0].x, &t[0].y, &t[1].x, &t[1].y, &t[2].x, &t[2].y) > 0){int n = 0;double maxx, minx, maxy, miny;Point scan;if(area2(t[0], t[2], t[1]) > 0){a = t[0];b = t[1];c = t[2];}else{a = t[0];b = t[2];c = t[1];}maxx = minx = a.x;maxy = miny = a.y;if(b.x > maxx){maxx = b.x;}if(c.x > maxx){maxx = c.x;}if(b.x < minx){minx = b.x;}if(c.x < minx){minx = c.x;}if(b.y > maxy){maxy = b.y;}if(c.y > maxy){maxy = c.y;}if(b.y < miny){miny = b.y;}if(c.y < miny){miny = c.y;}maxx = floor(maxx);minx = ceil(minx);maxy = floor(maxy);miny = ceil(miny);for(int i = minx; i <= maxx; i++){for(int j = miny; j <= maxy; j++){scan.x = i;scan.y = j;if(area2(a, scan, b)>0 && area2(a, c, scan)>0 && area2(scan, c, b)>0)n++;}}printf("%d\n", n);}return 0;}
有勇气并不表示恐惧不存在，而是敢面对恐惧克服恐惧
