merkator

not full b problem

Mar 31st, 2011
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.21 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 ""
  11. //#define strings
  12.  
  13. //Standart
  14. #include<cstdlib>
  15. #include<cstdio>
  16. #include<cctype>
  17. #include<iostream>
  18. #include<cmath>
  19.  
  20. //STL
  21. #ifdef stl
  22. #include<algorithm>
  23. #include<vector>
  24. #include<stack>
  25. #include<deque>
  26. #include<queue>
  27. #include<utility>
  28. #include<functional>
  29. #include<map>
  30. #include<set>
  31. #endif
  32.  
  33. //Strings
  34. #ifdef strings
  35. #include<string>
  36. #include<cstring>
  37. #endif
  38.  
  39. //Loops
  40. #define forn(i, n) for(int i = 0; i < n; ++i)
  41. #define forb(i, n) for(int i = n; i > 0; --i)
  42. #define forab(i, a, b) for(int i = a; i < b; ++i)
  43.  
  44. //Acronyms
  45. #define pb push_back
  46. #define mp make_pair
  47.  
  48. using namespace std;
  49.  
  50. struct pt{
  51.         int x, y;
  52.         pt(){
  53.         }
  54.         ;
  55.         pt(int a, int b){
  56.             x = a;
  57.             y = b;
  58.         }
  59.         ;
  60. };
  61.  
  62. #undef taskname
  63.  
  64. vector<pt> hull[2];
  65.  
  66. bool PointInPolygon(vector<pt> &poly, pt t){
  67.     bool c = 0;
  68.     int len = poly.size();
  69.     for(int i = 0, j = len - 1; i < n; j = i++){
  70.         if(((poly[i].y < poly[j].y) && (poly[i].y <= t.y) && (t.y <= poly[j].y)
  71.                 && ((poly[j].y - poly[i].y) * (t.x - poly[i].x) > (poly[j].x
  72.                         - poly[i].x) * (t.x - poly[i].y))) || ((poly[i].y
  73.                 > poly[j].y) && (poly[j].y <= t.y) && (t.y <= poly[i].y)
  74.                 && ((poly[j].y - poly[i].y) * (t.x - poly[i].x) < (poly[j].x
  75.                         - poly[i].x) * (t.y - poly[i].y)))){
  76.             c = !c;
  77.         }
  78.     }
  79.     return c;
  80. }
  81.  
  82. int main(){
  83. #ifdef taskname
  84.     freopen(taskname".in", "r", stdin);
  85.     freopen(taskname".out", "w", stdout);
  86. #endif
  87.     int n;
  88.     scanf("%d", &n);
  89.     forn(i, n) {
  90.         forn(j, 2) {
  91.             int vertnum;
  92.             scanf("%d", vertnum);
  93.             forn(k, vertnum) {
  94.                 pt t;
  95.                 scanf("%d%d", &t.x, &t.y);
  96.                 hull[j].pb(t);
  97.             }
  98.         }
  99.         bool ok = 0;
  100.         forn(j, 2) {
  101.             forn(k, hull[j].size()) {
  102.                 ok = PointInPolygon(hull[!j], hull[j][k]);
  103.                 if(ok){
  104.                     printf("YES\n");
  105.                     break;
  106.                 }
  107.             }
  108.             if(ok) break;
  109.         }
  110.         if(!ok){
  111.            
  112.         }
  113.     }
  114.     return 0;
  115. }
Advertisement
Add Comment
Please, Sign In to add comment