计算几何

#include<bits/stdc++.h> #define endl '\n' using namespace std; const double eps=1e-6; int nexta[8][2]={{0,1},{0,-1},{1,1},{1,-1},{1,0},{-1,0},{-1,1},{-1,-1}}; int n; struct Point { double x,y; Point(double xx = 0,double yy = 0):x(xx),y(yy) { } Point operator-(const Point & p) const { return Point(x-p.x,y-p.y); } }; typedef Point Vector; Point operator +(Point a, Vector p) { return Point(a.x + p.x, a.y + p.y); } double Cross(const Vector & v1, const Vector & v2) { //?? return v1.x * v2.y - v1.y * v2.x; } bool IsFormalCross(Point p1, Point p2, Point p3, Point p4) { return Cross(p2 - p1, p3 - p1)* Cross(p2 - p1, p4 - p1) < -eps && Cross(p4 - p3, p1 - p3)* Cross(p4 - p3, p2 - p3) < -eps; } Point San[5]; bool IsPointInPolygon(Point pt) { int i,j; bool c=false; for (i=0,j=2;i<3;j=i,i++) { if ((((San[i].y <= pt.y)&&(pt.y<San[j].y))|| ((San[j].y <= pt.y) && (pt.y < San[i].y))) &&(pt.x<(San[j].x-San[i].x)*(pt.y-San[i].y)/(San[j].y-San[i].y)+San[i].x)) { c=!c; } } return c; } char help[55][55]; char mapa[55][55]; bool book[55][55]; struct ha { int step; int x,y; }Q[500005]; int main() { while(~scanf("%d",&n)) { int a,b,c,d; for(a=0;a<3;a++) cin>>San[a].x>>San[a].y; for(a=0;a<n;a++) scanf("%s",help[a]); for(a=0;a<n;a++) { for(b=0;b<n;b++) { mapa[a][b]=help[n-1-b][a]; } } memset(book,0,sizeof book); int head=1,tail=2; Q[head].x=0,Q[head].y=0; Q[head].step=0; book[0][0]=1; bool flag=false; int ans=0; while(head<tail) { ha tmp=Q[head++]; int x=tmp.x,y=tmp.y; int k; for(k=0;k<8;k++) { int tx=x+nexta[k][0]; int ty=y+nexta[k][1]; if(tx>=n||ty>=n||tx<0||ty<0||mapa[tx][ty]=='#'||book[tx][ty]) continue; Point p1= Point(1.0*x,1.0*y); Point p2= Point(1.0*tx,1.0*ty); for(a=0;a<=2;a++) if(IsFormalCross(p1, p2, San[a], San[(a+1)%3])) { continue; } if(IsPointInPolygon(p2)) continue; Q[tail].step=tmp.step+1; Q[tail].x=tx; Q[tail].y=ty; book[tx][ty]=1; tail++; if(tx==n-1&&ty==n-1) { flag=true; ans=tmp.step+1; break; } } if(flag) break; } if(flag) printf("%d\n",ans); else puts("-1"); } return 0; }