# 计算几何

• c9998118
了解作者
• C/C++
开发工具
• 1.2KB
文件大小
• zip
文件格式
• 0
收藏次数
• 1 积分
下载积分
• 0
下载次数
• 2022-05-25 14:07
上传日期

Ans7.zip
• Ans7.cpp
2.4KB

#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; }

相关推荐
• wykobi计算几何
wykobi计算几何库，c++模板实现。使用简单，小巧，易集成。
• 计算几何C语言描述
计算几何在计算机领域有很广阔的用途，希望对大家有帮助
• 计算几何算法
计算几何算法。其中OpenGIS算法包含众多的算法，好用
• 北大POJ初级-计算几何
北大POJ初级-计算几何学 解题报告+AC代码
• MATLAB计算几何
MATLAB计算几何，包括几何图元的关系运算、点集的凸包、Delaunay剖分和Voronoi图等内容。
• 计算几何
具有用于计算几何的不同算法的存储库。 安装 要运行代码，应具备的所有内容-具有tkinter支持的Python> = 3.6。 通常，要启动项目，您应该： 使用git clone ...
• 计算几何算法
计算几何中涉及到的算法，包括向量相交的特征值的算法，线性方程组的迭代解法，环内外的确定
• 计算几何算法概览
计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题...在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。
• 计算几何 源码
计算几何 目录 ㈠ 点的基本运算 1. 平面上两点之间距离 1 2. 判断两点是否重合 1 3. 矢量叉乘 1 4. 矢量点乘 2 5. 判断点是否在线段上 2 6. 求一点饶某点旋转后的坐标 2 7. 求矢量夹角 2 ㈡ 线段及...
• libiconv-1.1.tar.gz
字符集转换程序