2017北京区域赛 G - Liaoning Ship’s Voyage【计算几何+bfs】

题目大意：一个图上有n*n个点，然后从起点走到终点，然后需要绕过三角形和“#”，问一个最短路径
分析：由于边上的点和端点都是能走的，我在扩展边的时候，判断该边与三角形是否有焦点，我原先是判断线段与线段的交点，然后判断点是否在三角形内部，后来发现如果一个线段的起点和终点都不在三角形内部的话，也是有可能穿过三角形的，所以后来我们枚举了线段上的100个点，判断是否在三角形内部

#include <bits/stdc++.h>
using namespace std;
char mp[50][50];
int dist[50][50];
const int inf=0x3f3f3f3f;
double eps=1e-8;
int n;
struct point
{
    double x,y;
    point(double X=0,double Y=0)
    {
        x=X,y=Y;
    }
};
point operator +(point a,point b)
{
    return point(a.x+b.x,a.y+b.y);
}
point operator -(point a,point b)
{
    return point(a.x-b.x,a.y-b.y);
}
point operator *(point a,double p)
{
    return point(a.x*p,a.y*p);
}
point operator /(point a,double p)
{
    return point(a.x/p,a.y/p);
}
double len(point a)
{
    return sqrt(a.x*a.x+a.y*a.y);
}
double dot(point a,point b)
{
    return a.x*b.x+a.y*b.y;
}
double cross(point a,point b)
{
    return a.x*b.y-a.y*b.x;
}
int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    else return x<0?-1:1;
}
bool operator == (point a,point b)
{
    if(dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0)return true;
    else return false;
}
bool segment(point a,point b,point c,point d)
{
    double c1 = cross(b-a,c-a);
    double c2 = cross(b-a,d-a);
    double d1 = cross(d-c,a-c);
    double d2 = cross(d-c,b-c);
    return dcmp(c1)*dcmp(c2)<0&&dcmp(d1)*dcmp(d2)<0;
}
double dists(point p,point a,point b)
{
    if(a==b) return len(p-a);
    point v1 = b-a,v2 = p-a,v3=p-b;
    if(dcmp(dot(v1,v2))<0) return len(v2);
    else if(dcmp(dot(v1,v3))>0) return len(v3);
    return fabs(cross(v1,v2))/len(v1);
}
point tri[5];
int pointin(point p,point *a,int n)
{
    int wn = 0,k,d1,d2;
    for(int i=1; i<=n; i++)
    {
        if(dcmp(dists(p,a[i],a[i%n+1]))==0) return 0;
        k = dcmp(cross(a[i%n+1]-a[i],p-a[i]));
        d1 = dcmp(a[i].y-p.y);
        d2 = dcmp(a[i%n+1].y-p.y);
        if(k>0&&d1<=0&&d2>0) wn++;
        if(k<0&&d2<=0&&d1>0) wn--;
    }
    if(wn) return 1;
    else return 0;
}
bool check(int x,int y,int fx,int fy)
{
    if(fx<0||fx>=n||fy<0||fy>=n)return false;
    if(mp[x][y]=='#'||mp[fx][fy]=='#')return false;
    point a,b,c;
    a.x=y;
    a.y=x;
    b.x=fy;
    b.y=fx;
    for(int i=1; i<=3; i++)
    {
        if(segment(a,b,tri[i],tri[i%3+1])) return false;
    }
    if(pointin(a,tri,3)) return false;
    if(pointin(b,tri,3)) return false;
    for(int i=1;i<=100;i++)
    {
        double p = i*0.01;
        c.x=a.x+(b.x-a.x)*p;
        c.y = a.y+(b.y-a.y)*p;
        if(pointin(c,tri,3)) return false;
    }
    return true;
}
int fx[8] = {0, 0, 1,-1, 1, 1,-1,-1};
int fy[8] = {1,-1, 0, 0, 1,-1, 1,-1};
int d[500];
bool bfs(int s, int t)
{
    memset(d,-1,sizeof(d));
    queue<int> q;
    q.push(s*n+t);
    d[s*n+t]=0;
    while(!q.empty())
    {
        int u  = q.front();
        q.pop();
        int x = u/n;
        int y = u%n;
        if(u == n*n-1)  return true;
        for(int i = 0; i < 8; i++)
        {
            int fx1 = x + fx[i];
            int fy1 = y + fy[i];
            if(check(x,y,fx1,fy1) && d[fx1*n+fy1] == -1)
            {
                d[fx1*n+fy1] = d[u] + 1;
                q.push(fx1*n+fy1);
            }
        }
    }
    return false;
}


int main()
{

    while(~scanf("%d",&n))
    {
        for(int i=1; i<=3; i++)
        {
            scanf("%lf%lf",&tri[i].x,&tri[i].y);
        }
        /*point st=point(1.5,1);
        cout<<pointin(st,tri,3)<<endl;*/
        for(int i=n-1; i>=0; i--)
        {
            scanf("%s",mp[i]);
        }
        if(bfs(0,0))
        {
            printf("%d\n",d[n*n-1]);
        }
        else printf("-1\n");
    }
    return 0;
}
/*
4
1 1 2 2 0 2
#...
#.##
#.##
..##


*/