首页 > 代码库 > hlg1429凸多边形 二分+叉积

hlg1429凸多边形 二分+叉积

2024-07-02 01:33:40   225人阅读

凸多边形
Time Limit: 2000 MS Memory Limit: 65536 K
Total Submit: 154(27 users) Total Accepted: 50(22 users) Rating:  Special Judge: No
Description

已知一个凸多边形A（包含n个点，点按照顺时针给出），和一个点集B（包含m个点），请判断这m个点是否都严格在凸多边形A内部。

Input

输入包含多组测试数据。

对于每组测试数据：

第1行，包含一个整数n (3?≤ n ≤?105)代表着凸多边形A的点的数量。

接下来n行每行包含一个坐标(x, y) (-109 ≤ x, y ≤?109) 表示这个凸多边形，点按照顺时针给出。

第n + 2行，包含一个整数m (3?≤ m ≤?105)代表着点集B的点的数量。

接下来m行每行包含一个坐标(x, y) (-109 ≤ x, y ≤?109) 表示这个点集B。

处理到文件结束

Output

对于每组测试数据：

第1行，如果点集B都严格在凸多边形A内，输出YES，否则输出NO。

Sample Input

4

-10 -10

-10 10

10 10

10 -10

3

0 0

1 1

2 2

4

-10 -10

-10 10

10 10

10 -10

3

100 100

1 1

2 2

Sample Output

YES

NO

Author
齐达拉图@HRBUST

思路：二分+叉积

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 100005;
 8 typedef long long LL;
 9 
10 struct Node
11 {
12     LL x;
13     LL y;
14 }node1[maxn], node2[maxn];
15 
16 LL cross(Node n0, Node n1, Node n2)
17 {
18     return (n1.x - n0.x)*(n2.y - n0.y) - (n2.x - n0.x)*(n1.y - n0.y);
19 }
20 
21 int main()
22 {
23     int n, m;
24     while(scanf("%d",&n) != EOF)
25     {
26         for(int i = 0; i < n; i++)
27             scanf("%lld %lld",&node1[i].x, &node1[i].y);
28         scanf("%d",&m);
29         for(int i = 0; i < m; i++)
30             scanf("%lld %lld",&node2[i].x, &node2[i].y);
31         bool ans = true;
32         for(int i = 0; i < m;  i++)
33         {
34             if(cross(node1[0], node1[1], node2[i]) >= 0 || cross(node1[0], node1[n-1], node2[i]) <= 0)
35             {
36                 ans = false;
37                 break;
38             }
39             int front = 1, end = n - 1;
40             while(end - front != 1)
41             {
42                 int mid = (front + end)>>1;
43                 if(cross(node1[0], node1[mid], node2[i]) >= 0)
44                     end = mid;
45                 else
46                     front = mid;
47             }
48             if(cross(node1[front], node2[i], node1[end]) <= 0)
49             {
50                 ans = false;
51                 break;
52             }
53         }
54         if(ans)
55             printf("YES\n");
56         else
57             printf("NO\n");
58     }
59     return 0;
60 }

 


联系
我们