Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //============================================================================
- // Name : HullInter.cpp
- // Author : Michael Verkhovykh
- // Version :
- // Copyright : CC BY-SA
- // Description : Searching polygon intersections
- //============================================================================
- #define stl
- #define taskname ""
- //#define strings
- //Standart
- #include<cstdlib>
- #include<cstdio>
- #include<cctype>
- #include<iostream>
- #include<cmath>
- //STL
- #ifdef stl
- #include<algorithm>
- #include<vector>
- #include<stack>
- #include<deque>
- #include<queue>
- #include<utility>
- #include<functional>
- #include<map>
- #include<set>
- #endif
- //Strings
- #ifdef strings
- #include<string>
- #include<cstring>
- #endif
- //Loops
- #define forn(i, n) for(int i = 0; i < n; ++i)
- #define forb(i, n) for(int i = n; i > 0; --i)
- #define forab(i, a, b) for(int i = a; i < b; ++i)
- //Acronyms
- #define pb push_back
- #define mp make_pair
- using namespace std;
- struct pt{
- int x, y;
- pt(){
- }
- ;
- pt(int a, int b){
- x = a;
- y = b;
- }
- ;
- };
- #undef taskname
- vector<pt> hull[2];
- bool PointInPolygon(vector<pt> &poly, pt t){
- bool c = 0;
- int len = poly.size();
- for(int i = 0, j = len - 1; i < n; j = i++){
- if(((poly[i].y < poly[j].y) && (poly[i].y <= t.y) && (t.y <= poly[j].y)
- && ((poly[j].y - poly[i].y) * (t.x - poly[i].x) > (poly[j].x
- - poly[i].x) * (t.x - poly[i].y))) || ((poly[i].y
- > poly[j].y) && (poly[j].y <= t.y) && (t.y <= poly[i].y)
- && ((poly[j].y - poly[i].y) * (t.x - poly[i].x) < (poly[j].x
- - poly[i].x) * (t.y - poly[i].y)))){
- c = !c;
- }
- }
- return c;
- }
- int main(){
- #ifdef taskname
- freopen(taskname".in", "r", stdin);
- freopen(taskname".out", "w", stdout);
- #endif
- int n;
- scanf("%d", &n);
- forn(i, n) {
- forn(j, 2) {
- int vertnum;
- scanf("%d", vertnum);
- forn(k, vertnum) {
- pt t;
- scanf("%d%d", &t.x, &t.y);
- hull[j].pb(t);
- }
- }
- bool ok = 0;
- forn(j, 2) {
- forn(k, hull[j].size()) {
- ok = PointInPolygon(hull[!j], hull[j][k]);
- if(ok){
- printf("YES\n");
- break;
- }
- }
- if(ok) break;
- }
- if(!ok){
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment