bfs肯定没问题了，
不过中间的判断非常恶心
关键是三角形
出题人：这题很容易怀疑人生
提供几组数据(from zm)
2
0 0
0 2
2 0
..
..
2
1 1
0 1
1 0
..
..
2
0.5 0.5
0.5 1.5
1.5 0.5
..
..
计算几何的边界好搞啊
#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long LL;
using namespace std;
const int N = 22;
const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
struct point{
double x, y;
point():x(0), y(0){}
point(double _x, double _y): x(_x),y(_y){}
inline void read(){
scanf("%lf%lf", &x, &y);
}
point operator + (const point &a) const {
return point(x+a.x, y+a.y);
}
point operator - (const point &a) const {
return point(x-a.x, y-a.y);
}
point operator * (const double &k) const {
return point(x * k, y * k);
}
double operator ^ (const point &a) const { // det
return x*a.y - y*a.x;
}
double dis(const point &b) {
return (x-b.x)*(x-b.x) + (y-b.y)*(y-b.y);
}
inline void print(){
printf("point: (%.2lf, %.2lf)
", x, y);
}
bool onSeg(point P1, point P2){
point Q = point(x, y);
if (min(P1.x,P2.x) > Q.x || Q.x > max(P1.x,P2.x)) return false;
if (min(P1.y,P2.y) > Q.y || Q.y > max(P1.y,P2.y)) return false;
double ans = fabs((Q - P1) ^ (Q - P2));
//printf("??? = %.4lf
", ans);
if (fabs((Q - P1) ^ (Q - P2)) > 0) return false;
return true;
}
} A, B, C;
double s(point p, point a, point b){
return fabs((p - a) ^ (p - b));
}
bool inTra(point P, point A, point B, point C){
double s1 = s(P, A, B), s2 = s(P, B, C), s3 = s(P, C, A);
if (s1 == 0 || s2 == 0 || s3 == 0) return false;
double a = s1 + s2 + s3;
double b = s(A, B, C);
//printf("%.2lf
", a-b);
return fabs(a - b) == 0.;
}
bool segXseg(point p1, point p2, point p3, point p4){
if (p1.onSeg(p3, p4) || p2.onSeg(p3, p4)) return false;
if (p3.onSeg(p1, p2) || p4.onSeg(p1, p2)) return false;
//---------------------------------------------
if (max(p1.x, p2.x) < min(p3.x, p4.x)) return 0;
if (max(p1.y, p2.y) < min(p3.y, p4.y)) return 0;
if (max(p3.x, p4.x) < min(p1.x, p2.x)) return 0;
if (max(p3.y, p4.y) < min(p1.y, p2.y)) return 0;//ju xin shi yan
double x = (p3 - p1) ^ (p2 - p1);
double y = (p4 - p1) ^ (p2 - p1);
double z = (p1 - p3) ^ (p4 - p3);
double w = (p2 - p3) ^ (p4 - p3); //KuaLi
return x*y <= 0 && z*w <= 0;
}
bool xj(point p1, point p2, point A, point B, point C){ //xiangjiao
//for (double k = 0.01; k < 1; k += 0.01)
//if (inTra((p1*k + p2*(1-k)), A, B, C)) return true;
if (inTra(p1*0.01 + p2*0.99, A, B, C)) return true;
if (inTra(p1*0.99 + p2*0.01, A, B, C)) return true;
if (segXseg(p1, p2, A, B)) return true;
if (segXseg(p1, p2, A, C)) return true;
if (segXseg(p1, p2, C, B)) return true;
return false;
}
bool wea[N][N]; // weather
bool vis[N][N];
int step[N][N];
int bfs(const int &n, int sx, int sy){
if (!wea[sx][sy]) return -1;
memset(vis, false, sizeof vis);
vis[sx][sy] = true;
step[sx][sy] = 0;
queue <point> Q;
for (Q.push(point(sx, sy)); !Q.empty();){
point p = Q.front(); Q.pop();
if (p.x == n-1 && p.y == n-1) return step[n-1][n-1];
for (int i = 0; i < 8; i++){
int cx = (int)p.x + dx[i];
int cy = (int)p.y + dy[i];
if (cx < 0 || cx >= n|| cy < 0 || cy >= n) continue;
if (!wea[cx][cy] || vis[cx][cy]) continue; //weather
if (xj(p, point(cx, cy), A, B, C)) continue;
step[cx][cy] = step[(int)p.x][(int)p.y] + 1;
vis[cx][cy] = true;
//printf("-----------(%d, %d)->(%d, %d), %d
", (int)p.x, (int)p.y, cx, cy, step[cx][cy]);
Q.push(point(cx, cy));
}
}
return -1;
}
int main(){
//freopen("in.txt", "r", stdin);
char ch;
for (int n; ~scanf("%d", &n);){
A.read(); B.read(); C.read();
memset(wea, true, sizeof wea);
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j++) if (inTra(point(i, j), A, B, C)) {
//printf("%d, %d
", i, j);
wea[i][j] = false;
}
scanf("
");
for (int j = n-1; j >= 0; j--){
for (int i = 0; i < n; i++){
scanf("%c", &ch);
if (ch == '#') wea[i][j] = false;
}
scanf("
");
}
int ans = bfs(n, 0, 0);
printf("%d
", ans);
}
return 0;
}