merkator

81 points

Mar 31st, 2011
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.42 KB | None | 0 0
  1. //============================================================================
  2. // Name        : HullInter.cpp
  3. // Author      : Michael Verkhovykh
  4. // Version     :
  5. // Copyright   : CC BY-SA
  6. // Description : Searching polygon intersections
  7. //============================================================================
  8.  
  9. #define stl
  10. #define taskname "intersect"
  11. //#define strings
  12.  
  13. //Standart
  14. #include<cstdlib>
  15. #include<cstdio>
  16. #include<cctype>
  17. #include<iostream>
  18. #include<cmath>
  19. #include<cassert>
  20.  
  21. //STL
  22. #ifdef stl
  23. #include<algorithm>
  24. #include<vector>
  25. #include<stack>
  26. #include<deque>
  27. #include<queue>
  28. #include<utility>
  29. #include<functional>
  30. #include<map>
  31. #include<set>
  32. #endif
  33.  
  34. //Strings
  35. #ifdef strings
  36. #include<string>
  37. #include<cstring>
  38. #endif
  39.  
  40. //Loops
  41. #define forn(i, n) for(int i = 0; i < n; ++i)
  42. #define forb(i, n) for(int i = n; i > 0; --i)
  43. #define forab(i, a, b) for(int i = a; i < b; ++i)
  44.  
  45. //Acronyms
  46. #define pb push_back
  47. #define mp make_pair
  48.  
  49. using namespace std;
  50.  
  51. struct pt{
  52.         int x, y;
  53.         pt(){
  54.         }
  55.         pt(int a, int b){
  56.             x = a;
  57.             y = b;
  58.         }
  59. };
  60.  
  61. bool operator==(pt a, pt b){
  62.     return a.x == b.x && a.y == b.y;
  63. }
  64.  
  65. vector<pt> hull[2];
  66.  
  67. int inPoly(vector<pt> &poly, int xt, int yt){
  68.     int xnew, ynew;
  69.     int xold, yold;
  70.     int x1, y1;
  71.     int x2, y2;
  72.     int i;
  73.     int inside = 0;
  74.  
  75.     if(poly.size() < 3){
  76.         return (0);
  77.     }
  78.     int npoints = poly.size();
  79.     xold = poly[npoints - 1].x;
  80.     yold = poly[npoints - 1].y;
  81.     for(i = 0; i < npoints; i++){
  82.         if(poly[i] == pt(xt, y1)){
  83.             return 0;
  84.         }
  85.         xnew = poly[i].x;
  86.         ynew = poly[i].y;
  87.         if(xnew > xold){
  88.             x1 = xold;
  89.             x2 = xnew;
  90.             y1 = yold;
  91.             y2 = ynew;
  92.         }else{
  93.             x1 = xnew;
  94.             x2 = xold;
  95.             y1 = ynew;
  96.             y2 = yold;
  97.         }
  98.         if((xnew < xt) == (xt <= xold) && (yt - y1) * (x2 - x1) < (y2 - y1)
  99.                 * (xt - x1)){
  100.             inside = !inside;
  101.         }
  102.         xold = xnew;
  103.         yold = ynew;
  104.     }
  105.     return (inside);
  106. }
  107.  
  108. int square(pt a, pt b, pt c){
  109.     return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
  110. }
  111.  
  112. bool intersect_1(int a, int b, int c, int d){
  113.     return max(a, b) >= min(c, d) && max(c, d) >= min(a, b);
  114. }
  115.  
  116. bool intersect(pt a, pt b, pt c, pt d){
  117.     int s11 = square(a, b, c);
  118.     int s12 = square(a, b, d);
  119.     int s21 = square(c, d, a);
  120.     int s22 = square(c, d, b);
  121.     if(s11 == 0 && s12 == 0 && s21 == 0 && s22 == 0)
  122.         return intersect_1(a.x, b.x, c.x, d.x) && intersect_1(a.y, b.y, c.y,
  123.                 d.y);
  124.     else
  125.         return (s11 * s12 <= 0) && (s21 * s22 <= 0);
  126. }
  127.  
  128. int main(){
  129. #ifdef taskname
  130.     freopen(taskname".in", "r", stdin);
  131.     freopen(taskname".out", "w", stdout);
  132. #endif
  133.     int n;
  134.     scanf("%d", &n);
  135.     forn(i, n) {
  136.         forn(j, 2) {
  137.             int vertnum;
  138.             scanf("%d", &vertnum);
  139.             forn(k, vertnum) {
  140.                 pt t;
  141.                 scanf("%d%d", &t.x, &t.y);
  142.                 hull[j].pb(t);
  143.             }
  144.         }
  145.         bool ok = 0;
  146.         forn(j, 2) {
  147.             forn(k, hull[j].size()) {
  148.                 ok = inPoly(hull[!j], hull[j][k].x, hull[j][k].y);
  149.                 if(ok){
  150.                     printf("YES\n");
  151.                     break;
  152.                 }
  153.             }
  154.             if(ok)
  155.                 break;
  156.         }
  157. /*      if(!ok){
  158.             for(int i = 0, j = hull[0].size() - 1; i < hull[0].size(); j = i++){
  159.                 for(int k = 0, l = hull[1].size() - 1; k < hull[1].size(); l
  160.                         = k++){
  161.                     ok = intersect(hull[0][i], hull[0][j], hull[1][k],
  162.                             hull[1][l]);
  163.                     if(ok){
  164.                         printf("YES\n");
  165.                         break;
  166.                     }
  167.                 }
  168.                 if(ok){
  169.                     break;
  170.                 }
  171.             }
  172.         }*/
  173.         if(!ok){
  174.             printf("NO\n");
  175.         }
  176.         hull[0].clear();
  177.         hull[1].clear();
  178.     }
  179.     return 0;
  180. }
Advertisement
Add Comment
Please, Sign In to add comment