本文主要是介绍hdu 2872 Another Snake 爆搜 判断射线与线段相交，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意： 给出n各点，有一条蛇从原点开始走。每次只能向左 [0,180) 转。并且不能和原路径相交。走到最后一个点后会一直往前走。问最多能走到的点数
假设现在走到的点为p，下一个点q。如果射线pq 与之前的路径相交了，由于只能左转，之后无论怎么走，最终必然会与路径相交，因此此时走pq是不合法的。
合理的方案数是很少的，可以暴力的搜索。
每次只要判断 射线是否与原路径相交，是否为向左转即可。
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<string>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
void fre(){freopen("t.txt","r",stdin);}
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
const int MAXN = 1<<30;
const int N = 50000;
const double eps = 1e-16;
int sgn(double x)
{if(fabs(x) < eps) return 0;if(x < 0) return -1;else return 1;
}
struct Point
{double x,y;Poi这篇关于hdu 2872 Another Snake 爆搜 判断射线与线段相交的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
