L3-018 森森美图 (30 分)

题目

题目链接

题解

BFS。

先看看样例咋出来的吧。

判断某个坐标属于起点终点连线的哪一侧的时候，我们采用是将点代入起点终点的两点式中根据正负值判断，两次bfs更新起点到终点的“距离”。

bfs每次扩展一个点，用起点到该点的“距离”更新其八个方向上的点的“距离”，如果八个方向上的点保存的“距离”被更新了，则入队，可以用这些点继续更新别的点，否则不要入队了，因为别的点已经由这些点更新过了，再加入个没变的“距离”还是不会有任何效果的，所以直接不入队，节约时间。

坑点：

1. 注意不要重复统计起点和终点。（这个点因为我瞎眼，卡了也就将近俩小时吧）
2. 注意x是轴是水平方向，y轴是竖直方向，所以列的变化方向为x轴变化方向，行的变化方向为y轴变化方向。我采用的方法是转置，因为还是觉得常见的保存方式做起来比较顺手（顺手：指debug两个半小时）

补充几点：

已知三角形三个顶点，计算三角形面积可以使用行列式：

当然，加上绝对值才算面积，也可以计算这个行列式的正负来判断属于直线的不同侧，展开再合并可以得到两点式的变形。

（实在懒得写Latex了，就截了个）

下面的程序中注释掉的代码部分为输出路径的语句，如果不理解可以输出看看。

我他妈服了，ljPTA题目描述真恶心，废话多而且描述的还不清楚，限制还贼多。

最后，感谢大佬的博客，如果不是大佬的博客，我可能永远都不知道样例是咋算出来的。

代码

#include
#define PII pair
using namespace std;

const double C = sqrt(2) - 1, MAX_DOUBLE = 1e50;
const int N = 110;

int n, m, flag;
int stx, tax, sty, tay;
//PII path[N][N];
double a[N][N], w[N][N];

double ans;

bool check (int x, int y) {
	// 判断是否为直线的flag一侧
	// 当(x,y)为终点时也要特殊判断返回的是可行，即属于flag一侧 
	double area =  (tax-stx) * (y-sty) - (tay-sty) * (x-stx);
	if (flag * area > 0 || (x == tax && y == tay)) return true;
	return false; 
}

void bfs () {
	// 初始化 
	for (int i = 0;i > tay;  
	
	// 注释部分为路径输出 
//	memset (path, -1, sizeof path);
	flag = -1; bfs (); ans += w[tax][tay]; // 因为通过公式计算得到的值可能为正值或负值，通过flag控制属于直线的哪一侧 
//	cout