题意:给你一个20*20的地图,起点(0,0),终点(n-1,n-1),有障碍的点为‘#’,每次可以向8个方向走一步,还给了一个三角形,除了障碍以外,到这8个方向上的点的线段如果没有与三角形相交,那么就可以到达,问最少步数

题解:主要是判断线段与三角形的相交,去年在现场和大多题解都是慢慢讨论,因为这个线段其实可以在边上,可以与三角形有交点,

         今天重现才想到,只需要线段上有一点在三角形内部就不能走,坐标范围不大,直接枚举线段上200个点,挨着判断就行

         在判断点在三角形内部时,注意顺时针逆时针啊,板子注意啊

       

1 #include
     
        2 const int inf=0x7fffffff/3;  3 const double eps=1e-7;  4 using namespace std;  5 int dcmp(double x)  6 {  7     return (x>eps)-(x<-eps);  8 }  9 struct point 10 { 11     double x,y; 12     point(){} 13     point(double x,double y):x(x),y(y){ } 14     point operator - (const point b){
   return point(x-b.x,y-b.y);} 15 }a[4]; 16 double dot(point a,point b){
   return a.x*b.x+a.y*b.y;} 17 double cross(point a,point b){
   return a.x*b.y-a.y*b.x;} 18  19 int n,m,t,h,en,dis[410],used[500]; 20 int id[22][22],p,head[500]; 21 char x[22]; 22 int dx[8]={
   0,1,1,1,0,-1,-1,-1}; 23 int dy[8]={
   1,1,0,-1,-1,-1,0,1}; 24 queue
      
       q; 25 struct rec 26 { 27     int go,next; 28 }eg[6000]; 29 void build(int a,int b) 30 { 31     p++; 32     eg[p].go=b; 33     eg[p].next=head[a]; 34     head[a]=p; 35 } 36 bool pointin(point p) 37 { 38     return dcmp(cross(a[1]-a[0],p-a[0]))>0 && dcmp(cross(a[2]-a[1],p-a[1]))>0 && dcmp(cross(a[0]-a[2],p-a[2]))>0; 39 } 40  41 bool check(point x,point y) 42 { 43     double ax=y.x-x.x; 44     double ay=y.y-x.y; 45     for (double i=1;i<=200;i=i+1.0) 46     { 47         point t; 48         t.x=x.x+ax/200.0*i; 49         t.y=x.y+ay/200.0*i; 50         if (pointin(t)==1) return 0; 51     } 52     return true; 53 } 54  55 void spfa(int n) 56 { 57     memset(used,0,sizeof(used)); 58     while (!q.empty())q.pop(); 59     for (int i=2;i<=n;i++) dis[i]=inf; 60     q.push(1); 61     used[1]=1; 62     dis[1]=0; 63     while (!q.empty()) 64     { 65         int x=q.front();q.pop(); 66         for (int u=head[x];u;u=eg[u].next) 67         { 68             int v=eg[u].go; 69             if (dis[x]+1
       
        =0;i--) 94         { 95             scanf("%s",x); 96             for (int j=0;j
        
         =n || ny<0 || ny>=n) continue;122                     if (check(point(j,i),point(ny,nx)))123                     {124                             //printf("%d %d\n",id[i][j],id[x][y]);125                         build(id[i][j],id[nx][ny]);126                     }127                 }128             }129 130         en=id[n-1][n-1];131         spfa(en);132         if (dis[en]==inf)puts("-1");else printf("%d\n",dis[en]);133     }134     return 0;135 }