首页 > 代码库 > 计算几何-点与多边形的位置判断-zoj1081Points Within
计算几何-点与多边形的位置判断-zoj1081Points Within
This article is made by Jason-Cow.
Welcome to reprint.
But please post the writer‘s address.
http://www.cnblogs.com/JasonCow/
叉积判方向
点积判角度
角度和=0°在外面
否则在里面
AC Code 这么短的计算几何,君难道不想收入囊中吗?
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <vector> 7 #include <cmath> 8 #include <queue> 9 #include <map> 10 #include <set> 11 using namespace std; 12 #define sqr(x) ((x)*(x)) 13 #define RG register 14 #define op operator 15 #define IL inline 16 #define db double 17 #define bl bool 18 const db pi=acos(-1.0),eps=1e-10; 19 struct D{db x,y;D(db x=0.0,db y=0.0):x(x),y(y){}}; 20 typedef D V; 21 V operator+(V A,V B){return V(A.x+B.x,A.y+B.y);} 22 V operator-(V A,V B){return V(A.x-B.x,A.y-B.y);} 23 V operator*(V A,db N){return V(A.x*N,A.y*N);} 24 V operator/(V A,db N){return V(A.x/N,A.y/N);} 25 V Rotate(V A,db a){return V(A.x*cos(a)-A.y*sin(a),A.x*sin(a)+A.y*cos(a));} 26 int dcmp(db x){if(fabs(x)<eps)return 0;else return x>0?1:-1;} 27 bl OnSegment(D A,D B,D P){return dcmp((P.x-A.x)*(P.x-B.x))<=0&&dcmp((P.y-A.y)*(P.y-B.y))<=0;} 28 db Len(D A){return sqrt(A.x*A.x+A.y*A.y);} 29 db Cross(V A,V B){return A.x*B.y-A.y*B.x;} 30 db Dot(V A,V B){return A.x*B.x+A.y*B.y;} 31 db VectorAngle(V a,V b){return acos(Dot(a,b)/(Len(a)*Len(b)));} 32 33 bl InPolygon(D P,D*R,int n){ 34 db ans=0.0; 35 R[0]=R[n]; 36 for(int i=0;i<n;i++){ 37 D A=R[i],B=R[i+1]; 38 int cross=dcmp(Cross(A-P,B-P)); 39 if(cross==0){if(OnSegment(A,B,P))return true;} 40 else{ 41 db angle=VectorAngle(A-P,B-P); 42 ans+=(cross>0?angle:-angle); 43 } 44 } 45 return dcmp(ans)!=0; 46 } 47 const int maxn=(int)1e5+10; 48 D A[maxn]; 49 50 int main(){ 51 int n,m,cnt=0; 52 db a,b; 53 while(scanf("%d",&n)&&n){ 54 if(cnt!=0)puts(""); 55 printf("Problem %d:\n",++cnt); 56 scanf("%d",&m); 57 for(int i=1;i<=n;i++)scanf("%lf%lf",&A[i].x,&A[i].y); 58 for(int i=1;i<=m;i++){ 59 scanf("%lf%lf",&a,&b); 60 printf("%s\n",InPolygon(D(a,b),A,n)?"Within":"Outside"); 61 } 62 } 63 return 0; 64 }
计算几何-点与多边形的位置判断-zoj1081Points Within
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。