成都 广告公司网站建设,建设网站的网站叫什么男,qq登陆wordpress,动漫制作专业可以专升本吗在解析几何中#xff0c;我们大量的使用列方程求解未知量。但是在计算机计算的时候#xff0c;解析几何的算法因为使用除法过多可能会带来严重的精度误差#xff0c;所以简单来说#xff0c;计算几何使用了一些其他的等效的方法来解决这些问题。 这里先说一个比较基础的题目…在解析几何中我们大量的使用列方程求解未知量。但是在计算机计算的时候解析几何的算法因为使用除法过多可能会带来严重的精度误差所以简单来说计算几何使用了一些其他的等效的方法来解决这些问题。 这里先说一个比较基础的题目大意为给定一个点数为n的正方形点按照顺序给出给定m个点判断点是否在多边形内。 我们的判定方法是过给定的点做与x轴平行的一条射线方向无所谓计算其与多边形的交点个数如果是奇数个则在多边形内否则不在。 但是问题在于可能有一些特殊的情况比如说交点正好是一条边的下端点或者上端点。这里的处理方法是对于点在线段上的情况直接特判掉否则如果在上端点相交则视为相交下端点相交视为不相交。这个是没有问题的如果在形外那么一个端点会被计算两次或者不算结果一样。如果在形内那么对于两条边的交点必然是同时与一上一下端点相交没有影响。 至于判断点在线段上的方法用到的是向量的内积和外积。而一开始的图形面积处理用的是向量外积求图形面积的方法。这些做法以后补上…… 所以具体的思路就是首先构造出一个多边形计算一下它的有向面积如果0的话就把图形整体反过来。之后对于给定的每一个点枚举图形的所有边判断是否与其相交计算出交点个数之后判定是否在图形内部即可。 看一下代码。 #includecstdio
#includealgorithm
#includecstring
#includeiostream
#includecmath
#includeset
#includequeue
#define rep(i,a,n) for(int i a;i n;i)
#define per(i,n,a) for(int i n;i a;i--)
#define enter putchar(\n)
#define fr friend inlineusing namespace std;
typedef long long ll;
const int M 100005;
const int INF 1000000009;
const double eps 1e-6;int read()
{int ans 0,op 1;char ch getchar();while(ch 0 || ch 9){if(ch -) op -1;ch getchar();}while(ch 0 ch 9){ans * 10;ans ch - 0;ch getchar();}return ans * op;
}struct point
{double x,y;point(){}point(double kx,double ky) : x(kx),y(ky) {}fr point operator (const point ls,const point rs)// vector plus{return point(ls.x rs.x,ls.y rs.y);}fr point operator - (const point ls,const point rs)//vector minus{return point(rs.x - ls.x,rs.y - ls.y);}fr point operator * (const point p,const double a)//vector multi{return point(p.x * a,p.y * a);}fr double operator * (const point ls,const point rs)//calc area{return ls.x * rs.y - ls.y * rs.x;}fr double dot(const point ls,const point rs)//dot product{return ls.x * rs.x ls.y * rs.y;}
}q;inline bool check(const point u,const point v,const point p)
{double det (u - p) * (v - p);if(det ! 0) return 0;double D dot(u - p,v - p);return D 0;
}struct polygon
{int n;point p[M];void init(int x){n x;rep(i,0,n-1) scanf(%lf %lf,p[i].x,p[i].y);p[n] p[0];if(Area() 0) reverse(p,pn); p[n] p[0];}inline double Area() const{double res 0;rep(i,0,n-1) res p[i] * p[i1];return res;}bool inner(const point q){int cnt 0;rep(i,0,n-1){if(check(p[i],p[i1],q)) return 1;double d1 p[i].y - q.y,d2 p[i1].y - q.y;double det (p[i] - q) * (p[i1] - q);if((det 0 d1 0 d2 0) || (det 0 d1 0 d2 0)) cnt;}return cnt 1;}
}P;int t,n,m;int main()
{while(t){n read();if(!n) break;m read(),P.init(n);if(t ! 1) enter;printf(Problem %d:\n,t);while(m--){scanf(%lf%lf,q.x,q.y);if(P.inner(q)) printf(Within\n);else printf(Outside\n);}}return 0;
} 转载于:https://www.cnblogs.com/captain1/p/9955545.html