首页 > 代码库 > hlg1429凸多边形 二分+叉积
hlg1429凸多边形 二分+叉积
凸多边形 | ||||||
| ||||||
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。