Advertisement
Guest User

Untitled

a guest
Jun 8th, 2011
274
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.22 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <cassert>
  8. #include <vector>
  9.  
  10. #define pb push_back
  11.  
  12. using namespace std;
  13.  
  14. typedef long long int64;
  15.  
  16. template <class T>
  17. T abs(T a){
  18.     return (a<0)?(-a):(a);
  19. }
  20.  
  21. struct point{
  22.     int64 x,y;
  23.     point():x(0),y(0){
  24.     }
  25.     point(int64 x,int64 y):x(x),y(y){
  26.     }
  27.     void load(){
  28.         int X,Y;
  29.         scanf("%d%d",&X,&Y);
  30.         x=X;y=Y;
  31.     }
  32. };
  33.  
  34. point operator-(const point& a,const point& b){
  35.     return point( a.x - b.x, a.y - b.y);
  36. }
  37.  
  38. point operator+(const point& a,const point& b){
  39.     return point( a.x + b.x, a.y + b.y);
  40. }
  41.  
  42. point operator*(const point& a,int b){
  43.     return point( a.x * b, a.y * b);
  44. }
  45.  
  46. int64 operator*(const point& a,const point& b){
  47.     return a.x * b.y - a.y * b.x;
  48. }
  49.  
  50. bool operator<(const point& a,const point& b){
  51.     if (a.y * b.y < 0)
  52.         return a.y > 0;
  53.     if (a.y * b.y == 0){
  54.         if (a.y < 0)
  55.             return false;
  56.         if (b.y < 0)
  57.             return true;
  58.         if (a.y ==0 && b.y ==0)
  59.             return a.x > 0 && b.x < 0;
  60.     }
  61.     return a*b > 0;
  62. }
  63.  
  64. bool operator== (const point& a,const point& b){
  65.     return a.x == b.x && a.y == b.y;
  66. }
  67.  
  68. typedef vector<point> polygon;
  69.  
  70. void read(polygon& a){
  71.     int size;
  72.     scanf("%d",&size);
  73.     a.resize(size);
  74.     for (int i = 0; i < size; i++)
  75.         a[i].load();
  76. }
  77.  
  78. polygon a,b,c,result;
  79.  
  80. void toZero(polygon& a,point& start){
  81.     start = start + a[0];
  82.     for (int i = 1, sz = a.size(); i < sz; i++)
  83.         a[i] = a[i] - a[0];
  84.     a[0] = point(0,0);
  85. }
  86.  
  87. void toVector(polygon& a){
  88.     assert(a[0] == point(0,0));
  89.     int sz = a.size();
  90.     a.pb(a[0]);
  91.     for (int i = 0; i < sz; i++)
  92.         a[i]=a[i+1]-a[i];
  93.     a.pop_back();  
  94. }
  95.  
  96. void norm(polygon& a,point& start){
  97.     int n=a.size();
  98.     toZero(a,start);
  99.     toVector(a);
  100.     int mpos=0;
  101.     for (int i = 0; i < n; i++)
  102.         if (a[i] < a[mpos])
  103.             mpos = i;
  104.     for (int i = 0; i < mpos; i++)
  105.         start=start + a[i];
  106.     rotate(a.begin(), a.begin() + mpos, a.end());      
  107. }
  108.  
  109. void toPoint(polygon& a,point start){
  110.     int n = a.size();
  111.     a[0] = a[0] + start;
  112.     for (int i = 1; i < n; i++)
  113.         a[i] = a[i] + a[i-1];      
  114. }
  115.  
  116. point center;
  117. vector<point> checkpoints;
  118.  
  119. bool cmpxy(const point& a,const point& b){
  120.     if (a.y == b.y)
  121.         return a.x < b.x;
  122.     return a.y < b.y;
  123. }
  124.  
  125. void checkPrecalc(){
  126.     int n=result.size();
  127.     int minid = 0;
  128.     for (int i = 0; i < n; i++)
  129.         if (cmpxy(result[i], result[minid]))
  130.             minid = i;  
  131.     rotate(result.begin(), result.begin() + minid, result.end());
  132.     center = result[0];
  133.     for (int i = 0; i < n; i++)
  134.         result[i] = result[i] - center;
  135.     checkpoints=vector<point>(result.begin()+1,result.end());      
  136. }
  137.  
  138. bool inTriangle(const point& p,const point& a,const point& b,const point& c){
  139.     int64 s1 = abs((b - a) * (c - a));
  140.     int64 s2 = abs((a - p) * (b - p)) +
  141.                abs((b - p) * (c - p)) +
  142.                abs((c - p) * (a - p));
  143.     return s1 == s2;
  144. }
  145.  
  146. bool check(point p){
  147.     p = p * 3;
  148.     p = p - center;
  149.     if (p.y < 0)
  150.         return false;
  151.     if (p.y == 0 && p.x < 0)
  152.         return false;
  153.     if (p < checkpoints[0])
  154.         return false;
  155.     if (checkpoints.back() < p)
  156.         return false;
  157.     int id = lower_bound(checkpoints.begin(), checkpoints.end(), p) - checkpoints.begin();
  158.     for (int i = -1; i < 2; i++){
  159.         int id2= id + i;
  160.         if (id2 >= 0 && id2+1 < (int)checkpoints.size()){
  161.             if (inTriangle(p,point(0,0),checkpoints[id2],checkpoints[id2+1]))
  162.                 return true;
  163.         }
  164.     }
  165.     return false;  
  166. }
  167.  
  168. void deleteoneLine(polygon& a){
  169.     int n=a.size();
  170.     vector<point> res;
  171.     int sz = 0;
  172.     for (int i = 0; i < n; i++){
  173.         while ( (sz > 1) && ((res[sz-1] - res[sz-2]) * (a[i] - res[sz-1]) == 0)){
  174.             res.pop_back();
  175.             --sz;
  176.         }
  177.         res.pb(a[i]);
  178.         ++sz;
  179.     }
  180.     if ((res[1] - res[0]) * (res[0] - res[sz-1]) == 0)
  181.         res.erase(res.begin());
  182.     a=res;
  183. }
  184.  
  185.  
  186. int main(){
  187.     #ifdef LOCAL
  188.         freopen("input.txt","r",stdin);
  189.         freopen("output.txt","w",stdout);
  190.     #endif
  191.     read(a);
  192.     read(b);
  193.     read(c);
  194.     deleteoneLine(a);  
  195.     deleteoneLine(b);  
  196.     deleteoneLine(c);  
  197.  
  198.     point start(0,0);
  199.     norm(a, start);
  200.     norm(b, start);
  201.     norm(c, start);
  202.     result.insert(result.end(), a.begin(), a.end());
  203.     result.insert(result.end(), b.begin(), b.end());
  204.     result.insert(result.end(), c.begin(), c.end());
  205.     inplace_merge(result.begin(), result.begin() + a.size(), result.end() - c.size());  
  206.     inplace_merge(result.begin(), result.end() - c.size(), result.end());
  207.     toPoint(result,start);
  208. //  for (int i=0;i<result.size();i++)
  209. //      cerr << result[i].x <<" " << result[i].y << endl;
  210.     deleteoneLine(result);  
  211.     checkPrecalc();
  212.    
  213.     int m;
  214.     scanf("%d", &m);
  215.     for (int i = 0; i < m; i++){
  216.         point p;
  217.         p.load();
  218. //      cerr << p.x << " "<< p.y << endl;
  219.         if (check(p))
  220.             printf("YES\n");
  221.         else
  222.             printf("NO\n");
  223.     }
  224. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement