就是利用叉積的性質,如果向量A1到向量A2是順時針則叉積為負反之為正。
然後我們可以二分的判斷找到一個點恰被兩條射線夾在一起。
然後我們再判斷是否l,r這兩個點所連直線與點的關系。
具體資料可以參照這個BLOG https://www.cnblogs.com/yym2013/p/3673616.html
代碼 By:大奕哥
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=100005;
4 int x[N],y[N],n,m;
5 double eps=1e-10;
6 struct node{double a,b;}q[N],p[N];
7 double xmul(node a,node b,node c)
8 {
9 return (a.a-c.a)*(b.b-c.b)-(b.a-c.a)*(a.b-c.b);
10 }
11 void judge()
12 {
13 for(int i=1;i<=m;++i)
14 {
15
16 if(xmul(q[i],p[2],p[1])<=eps||xmul(q[i],p[n],p[1])>=-eps){
17 puts("NO");return;
18 }
19 int l=2,r=n;
20 while(r-l>1)
21 {
22 int mid=l+r>>1;
23 if(xmul(q[i],p[mid],p[1])>eps)l=mid;
24 else r=mid;
25 }
26 if(xmul(q[i],p[r],p[l])<=eps)
27 {
28 puts("NO");return;
29 }
30 }
31 puts("YES");
32 }
33 int main()
34 {
35 while(~scanf("%d",&n))
36 {
37 for(int i=1;i<=n;++i)scanf("%lf%lf",&p[i].a,&p[i].b);
38 scanf("%d",&m);
39 for(int i=1;i<=m;++i)scanf("%lf%lf",&q[i].a,&q[i].b);
40 judge();
41 }
42 return 0;
43 }
轉載于:https://www.cnblogs.com/nbwzyzngyl/p/8094143.html