本文主要是介绍2017北京ICPC -G - Liaoning Ship’s Voyage （HihoCoder - 1633）几何，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目网址https://cn.vjudge.net/problem/HihoCoder-1633
比赛的时候只是想到了，将三角形内部的点换成#，然后与三角形严格相交的走法的线段不可行，但是端点相交是可行的。
但是我们忽略了一种情况，就是端点与三角型相交，但是两个端点交于三角形的不同边，这种是错误的，后来我改了之后还想到了一种情况会wa，后来枚举情况，把我hy给搞懵了
看了看人家是怎么解决的（博客），发现人家思路很清晰：
case1：L的一个端点在外，一个在内。只要枚举L跟三角形所有边是否规范相交即可。
case2：L的两个端点都在三角形的边上，判断L的中点是否在三角形内部即可
case3：最难想到吧。。一个端点在边上，另一个端点经过了三角形的一个顶点，而且L的中点在三角形外部。。
只要将端点各自向内缩一小块即可。
但是后来发现自己的板子还用错了一个地方，就是判断点在线段上时，端点处应该也要判断一下的，但是我之前没有判断。
好了，终于ac了这个题了。
献上丑陋的代码：
#include <iostream>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <vector>
#include <cstdio>
#include <queue>
#include <cmath>using namespace std;
const int maxn = 25;
struct Point
{double x,y;Point(double xx=0,double yy =0){x =xx;y = yy;}
// void print()
// {
// cout<<x<<" "<<y<<endl;
// }};typedef Point Vector;
Vector operator+ (Vector A,Vector B)
{return Vector(A.x+B.x,A.y+B.y);
}
Vector operator -(Vector A,Vector B)
{return Vector(A.x-B.x,A.y-B.y);
}
Vector operator*(Vector A,double p)
{return Vector(A.x*p,A.y*p);
}
Vector operator/(Vector A,double p)
{return Vector(A.x/p,A.y/p);
}
bool operator <(const Point &a,const Point &b)
{return a.x<b.x||(a.x==b.x && a.y<b.y);
}
const double eps = 1e-8;
int dcmp(double x)
{if(fabs(x)<eps)return 0;elsereturn x<0?-1:1;
}
bool operator == (const Point& a,const Point &b)
{return dcmp(a.x-b.x)==0 && dcmp(a.y - b.y)==0;
}
double Dot(Vector A,Vector B)
{return A.x*B.x+A.y*B.y;
}
double Cross(Vector A,Vector B)
{return A.x*B.y - A.y*B.x;
}
bool SegmentProper(Point a1,Point a2,Point b1,Point b2)
{double c1= Cross(a2-a1,b1-a1),c2 = Cross(a2-a1,b2-a1);double c3 = Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;
}
///就是wa下面这里了，还要注意连端点一块判断
bool OnSegment(Point p,Point a1,Point a2)
{
// return dcmp(Cross(a1-p,a2-p))==0 && dcmp(Dot(a1-p,a2-p))<0;if(dcmp(Cross(a1-p,a2-p))==0 && dcmp(Dot(a1-p,a2-p))<0 ) return 1;return a1 == p || a2 == p;
}Point san[4];
int IsPointIN(Point p)
{int wn = 0;int n = 3;for(int i=0; i<n; i++){if(OnSegment(p,san[i],san[(i+1)%n]))return -1; //bianejieint k = dcmp(Cross(san[(i+1)%n]- san[i],p-san[i]));int d1 = dcmp(san[i].y-p.y);int d2 = dcmp(san[(i+1)%n].y-p.y);if(k>0 && d1<=0 && d2>0)wn++;if(k<0 && d2<=0 && d1>0)wn--;}if(wn!=0)return 1;//niebureturn 0;
}
int n;
char mp[maxn][maxn];
int dx[]= {0,0,1,-1,1,1,-1,-1};
int dy[]= {1,-1,0,0,-1,1,-1,1};
int vis[maxn][maxn];
struct node
{int x,y;int t;node(int xx=0,int yy=0,int tt=0){x =xx;y = yy;t =tt;}bool operator<(const node & s)const{return t>s.t;}
};
int oj1(int xx,int yy)
{if(xx>=0&&xx<n&&yy>=0&&yy<n&&!vis[xx][yy] && mp[xx][yy]=='.')return 1;return 0;
}
void change(Point &p1,Point &p2,double t)
{Vector v = p2-p1;p1 = p1 + v*t;v = v*(-1.0);p2 = p2 + v*t;
}
int oj2(int x,int y,int xx,int yy)
{Point p(x,y);Point p2(xx,yy);int ok1=0,ok2=0;for(int i=0; i<3; i++){if(SegmentProper(p,p2,san[i],san[(i+1)%3]))return 0;if(OnSegment(Point(x,y),san[i%3],san[(i+1)%3]))ok1 = 1;if(OnSegment(Point(xx,yy),san[i],san[(i+1)%3]))ok2 = 1;}if(ok1&&ok2){if(IsPointIN(Point((double)(xx+x)/2.0,(double)(yy+y)/2.0))==1)return 0;}change(p,p2,1e-3);if(IsPointIN(p)==1)return 0;if(IsPointIN(p2)==1)return 0;return 1;
}
int dfs(int a,int b)
{priority_queue<node> q;q.push(node(a,b,0));vis[0][0] = 1;while(q.size()){node a = q.top();q.pop();if(a.x==n-1&&a.y==n-1){return a.t;}for(int i=0; i<8; i++){int xx = a.x+dx[i];int yy = a.y+dy[i];if(!oj1(xx,yy))continue;if(!oj2(a.x,a.y,xx,yy))continue;vis[xx][yy] = 1;q.push(node(xx,yy,a.t+1));}}return -1;
}
char xx[maxn][maxn];
int main()
{while(~scanf("%d",&n)){memset(vis,0,sizeof(vis));for(int i=0; i<3; i++){scanf("%lf%lf",&san[i].x,&san[i].y);}//cout<<oj2(1,0,1,1)<<endl; //wa的数据for(int i=n-1; i>=0; i--)scanf("%s",xx[i]);for(int i=0; i<n; i++){for(int j=0; j<n; j++)mp[i][j] = xx[j][i];}for(int i=0; i<n; i++)for(int j=0; j<n; j++){if(IsPointIN(Point(i,j))==1){mp[i][j]='#';}}int ans = dfs(0,0);printf("%d\n",ans);}return 0;
}
/*
3
0 0
1 0.5
2 01 0
1 1
*/
这篇关于2017北京ICPC -G - Liaoning Ship’s Voyage （HihoCoder - 1633）几何的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
