Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Nguyen Huu Hoang Minh
- #include <bits/stdc++.h>
- #define sz(x) int(x.size())
- #define all(x) x.begin(),x.end()
- #define reset(x) memset(x, 0,sizeof(x))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define N 5005
- #define remain(x) if (x > MOD) x -= MOD
- #define ii pair<int, int>
- #define iiii pair< ii , ii >
- #define viiii vector< iiii >
- #define vi vector<int>
- #define vii vector< ii >
- #define bit(x, i) (((x) >> (i)) & 1)
- #define Task "test"
- #define int long long
- using namespace std;
- typedef long double ld;
- const int inf = 1e10;
- const int minf = -1e10;
- struct pt {
- long long x, y;
- pt() {}
- pt(long long _x, long long _y) : x(_x), y(_y) {}
- pt operator+(const pt &p) const { return pt(x + p.x, y + p.y); }
- pt operator-(const pt &p) const { return pt(x - p.x, y - p.y); }
- long long cross(const pt &p) const { return x * p.y - y * p.x; }
- long long dot(const pt &p) const { return x * p.x + y * p.y; }
- long long cross(const pt &a, const pt &b) const { return (a - *this).cross(b - *this); }
- long long dot(const pt &a, const pt &b) const { return (a - *this).dot(b - *this); }
- long long sqrLen() const { return this->dot(*this); }
- };
- bool lexComp(const pt &l, const pt &r) {
- return l.x < r.x || (l.x == r.x && l.y < r.y);
- }
- int sgn(long long val) { return val > 0 ? 1 : (val == 0 ? 0 : -1); }
- vector<pt> seq;
- pt translation;
- int n;
- bool pointInTriangle(pt a, pt b, pt c, pt point) {
- long long s1 = abs(a.cross(b, c));
- long long s2 = abs(point.cross(a, b)) + abs(point.cross(b, c)) + abs(point.cross(c, a));
- return s1 == s2;
- }
- void prepare(vector<pt> &points) {
- n = points.size();
- int pos = 0;
- for (int i = 1; i < n; i++) {
- if (lexComp(points[i], points[pos]))
- pos = i;
- }
- rotate(points.begin(), points.begin() + pos, points.end());
- n--;
- seq.resize(n);
- for (int i = 0; i < n; i++)
- seq[i] = points[i + 1] - points[0];
- translation = points[0];
- }
- int CCW(pt a, pt b){
- return a.x*b.y - a.y*b.x;
- }
- bool pointInConvexPolygon(pt point) {
- point = point - translation;
- if (seq[0].cross(point) != 1 &&
- sgn(seq[0].cross(point)) != sgn(seq[0].cross(seq[n - 1])))
- return false;
- if (seq[n - 1].cross(point) != 0 &&
- sgn(seq[n - 1].cross(point)) != sgn(seq[n - 1].cross(seq[0])))
- return false;
- //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ừ
- //point tới p0 và p1 tới p0
- if (seq[0].cross(point) == 0)
- return false;
- if (seq[n - 1].cross(point) == 0)
- return false;
- int l = 0, r = n - 1;
- while (r - l > 1) {
- int mid = (l + r) / 2;
- int pos = mid;
- if (seq[pos].cross(point) >= 0)
- l = mid;
- else
- r = mid;
- }
- int pos = l;
- //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
- pt L = seq[pos]+translation;
- pt R = seq[pos+1]+translation;
- pt X = point + translation;
- if (CCW(R-L,L-X)==0) return false;
- //
- return pointInTriangle(seq[pos], seq[pos + 1], pt(0, 0), point);
- }
- void readfile()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- if (fopen(Task".inp","r"))
- {
- freopen(Task".inp","r",stdin);
- //freopen(Task".out","w",stdout);
- }
- cin >> n;
- vector<pt> p;
- for(int i=1; i<=n; i++){
- int x, y; cin >> x >> y;
- p.pb({x,y});
- }
- prepare(p);
- }
- void proc()
- {
- int q; cin >> q;
- while (q--){
- int x, y; cin >> x >> y;
- if (pointInConvexPolygon({x,y})) cout << "YES \n";
- else cout << "NO \n";
- }
- }
- signed main()
- {
- readfile();
- proc();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement