Advertisement
MinhNGUYEN2k4

METARAIN

Jan 14th, 2022
673
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.87 KB | None | 0 0
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 5005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19. #define int long long
  20.  
  21. using namespace std;
  22.  
  23. typedef long double ld;
  24. const int inf = 1e10;
  25. const int minf = -1e10;
  26.  
  27. struct pt {
  28.     long long x, y;
  29.     pt() {}
  30.     pt(long long _x, long long _y) : x(_x), y(_y) {}
  31.     pt operator+(const pt &p) const { return pt(x + p.x, y + p.y); }
  32.     pt operator-(const pt &p) const { return pt(x - p.x, y - p.y); }
  33.     long long cross(const pt &p) const { return x * p.y - y * p.x; }
  34.     long long dot(const pt &p) const { return x * p.x + y * p.y; }
  35.     long long cross(const pt &a, const pt &b) const { return (a - *this).cross(b - *this); }
  36.     long long dot(const pt &a, const pt &b) const { return (a - *this).dot(b - *this); }
  37.     long long sqrLen() const { return this->dot(*this); }
  38. };
  39.  
  40. bool lexComp(const pt &l, const pt &r) {
  41.     return l.x < r.x || (l.x == r.x && l.y < r.y);
  42. }
  43.  
  44. int sgn(long long val) { return val > 0 ? 1 : (val == 0 ? 0 : -1); }
  45.  
  46. vector<pt> seq;
  47. pt translation;
  48. int n;
  49.  
  50. bool pointInTriangle(pt a, pt b, pt c, pt point) {
  51.     long long s1 = abs(a.cross(b, c));
  52.     long long s2 = abs(point.cross(a, b)) + abs(point.cross(b, c)) + abs(point.cross(c, a));
  53.     return s1 == s2;
  54. }
  55.  
  56. void prepare(vector<pt> &points) {
  57.     n = points.size();
  58.     int pos = 0;
  59.     for (int i = 1; i < n; i++) {
  60.         if (lexComp(points[i], points[pos]))
  61.             pos = i;
  62.     }
  63.     rotate(points.begin(), points.begin() + pos, points.end());
  64.  
  65.     n--;
  66.     seq.resize(n);
  67.     for (int i = 0; i < n; i++)
  68.         seq[i] = points[i + 1] - points[0];
  69.     translation = points[0];
  70. }
  71.  
  72. int CCW(pt a, pt b){
  73.     return a.x*b.y - a.y*b.x;
  74. }
  75.  
  76. bool pointInConvexPolygon(pt point) {
  77.     point = point - translation;
  78.     if (seq[0].cross(point) != 1 &&
  79.             sgn(seq[0].cross(point)) != sgn(seq[0].cross(seq[n - 1])))
  80.         return false;
  81.     if (seq[n - 1].cross(point) != 0 &&
  82.             sgn(seq[n - 1].cross(point)) != sgn(seq[n - 1].cross(seq[0])))
  83.         return false;
  84.  
  85.     //Kiếm tra điểm nằm trên cạnh, nếu điểm nằm trên cạnh cũng thỏa mãn, ta cần kiếm tra độ dài từ
  86.     //point tới p0 và p1 tới p0
  87.     if (seq[0].cross(point) == 0)
  88.         return false;
  89.     if (seq[n - 1].cross(point) == 0)
  90.         return false;
  91.  
  92.     int l = 0, r = n - 1;
  93.     while (r - l > 1) {
  94.         int mid = (l + r) / 2;
  95.         int pos = mid;
  96.         if (seq[pos].cross(point) >= 0)
  97.             l = mid;
  98.         else
  99.             r = mid;
  100.     }
  101.     int pos = l;
  102.  
  103.     //Kiểm tra trường hợp nằm trên cạnh l-r, xóa nếu điểm nằm trên cạnh cũng thỏa mãn
  104.     pt L = seq[pos]+translation;
  105.     pt R = seq[pos+1]+translation;
  106.     pt X = point + translation;
  107.     if (CCW(R-L,L-X)==0) return false;
  108.     //
  109.  
  110.     return pointInTriangle(seq[pos], seq[pos + 1], pt(0, 0), point);
  111. }
  112.  
  113. void readfile()
  114. {
  115.     ios_base::sync_with_stdio(false);
  116.     cin.tie(0);cout.tie(0);
  117.     if (fopen(Task".inp","r"))
  118.     {
  119.         freopen(Task".inp","r",stdin);
  120.         //freopen(Task".out","w",stdout);
  121.     }
  122.     cin >> n;
  123.     vector<pt> p;
  124.     for(int i=1; i<=n; i++){
  125.         int x, y; cin >> x >> y;
  126.         p.pb({x,y});
  127.     }
  128.     prepare(p);
  129. }
  130.  
  131. void proc()
  132. {
  133.     int q; cin >> q;
  134.     while (q--){
  135.         int x, y; cin >> x >> y;
  136.         if (pointInConvexPolygon({x,y})) cout << "YES \n";
  137.         else cout << "NO \n";
  138.     }
  139. }
  140.  
  141. signed main()
  142. {
  143.     readfile();
  144.     proc();
  145.     return 0;
  146. }
  147.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement