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 "intersect"
- //#define strings
- //Standart
- #include<cstdlib>
- #include<cstdio>
- #include<cctype>
- #include<iostream>
- #include<cmath>
- #include<cassert>
- //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;
- }
- };
- bool operator==(pt a, pt b){
- return a.x == b.x && a.y == b.y;
- }
- vector<pt> hull[2];
- int inPoly(vector<pt> &poly, int xt, int yt){
- int xnew, ynew;
- int xold, yold;
- int x1, y1;
- int x2, y2;
- int i;
- int inside = 0;
- if(poly.size() < 3){
- return (0);
- }
- int npoints = poly.size();
- xold = poly[npoints - 1].x;
- yold = poly[npoints - 1].y;
- for(i = 0; i < npoints; i++){
- if(poly[i] == pt(xt, y1)){
- return 0;
- }
- xnew = poly[i].x;
- ynew = poly[i].y;
- if(xnew > xold){
- x1 = xold;
- x2 = xnew;
- y1 = yold;
- y2 = ynew;
- }else{
- x1 = xnew;
- x2 = xold;
- y1 = ynew;
- y2 = yold;
- }
- if((xnew < xt) == (xt <= xold) && (yt - y1) * (x2 - x1) < (y2 - y1)
- * (xt - x1)){
- inside = !inside;
- }
- xold = xnew;
- yold = ynew;
- }
- return (inside);
- }
- int square(pt a, pt b, pt c){
- return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
- }
- bool intersect_1(int a, int b, int c, int d){
- return max(a, b) >= min(c, d) && max(c, d) >= min(a, b);
- }
- bool intersect(pt a, pt b, pt c, pt d){
- int s11 = square(a, b, c);
- int s12 = square(a, b, d);
- int s21 = square(c, d, a);
- int s22 = square(c, d, b);
- if(s11 == 0 && s12 == 0 && s21 == 0 && s22 == 0)
- return intersect_1(a.x, b.x, c.x, d.x) && intersect_1(a.y, b.y, c.y,
- d.y);
- else
- return (s11 * s12 <= 0) && (s21 * s22 <= 0);
- }
- 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 = inPoly(hull[!j], hull[j][k].x, hull[j][k].y);
- if(ok){
- printf("YES\n");
- break;
- }
- }
- if(ok)
- break;
- }
- /* if(!ok){
- for(int i = 0, j = hull[0].size() - 1; i < hull[0].size(); j = i++){
- for(int k = 0, l = hull[1].size() - 1; k < hull[1].size(); l
- = k++){
- ok = intersect(hull[0][i], hull[0][j], hull[1][k],
- hull[1][l]);
- if(ok){
- printf("YES\n");
- break;
- }
- }
- if(ok){
- break;
- }
- }
- }*/
- if(!ok){
- printf("NO\n");
- }
- hull[0].clear();
- hull[1].clear();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment