Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <bits/stdc++.h>
#define X first
#define Y second
#define long long long
const int N = 5050;
using namespace std;
typedef pair<int, int> ii;
void operator -= (ii& A, ii B) {A.X -= B.X; A.Y -= B.Y;}
bool CCW(ii &A, ii B, ii C) {C -= B; B -= A; return (long)B.X * C.Y >= (long)B.Y * C.X;}
int n, m;
ii a[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d %d", &a[i].X, &a[i].Y);
    scanf("%d", &m);
    ii b;
    while (m--) {
        scanf("%d %d", &b.X, &b.Y);
        bool inside = true; a[0] = a[n];
        for(int i = 1; i <= n; i++)
        if (CCW(a[i], a[i - 1], b)) {
            inside = false; break;
        }
        if (inside) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

Code mẫu của RR

#include <vector>
#include <iostream>
#include <cmath>
using namespace std;

const double EPS = 1e-6;

inline int cmp(double a, double b) {
    return (a < b - EPS) ? -1 : ((a > b + EPS) ? 1 : 0);
}

struct Point {
    double x, y;
    Point(double x = 0.0, double y = 0.0) : x(x), y(y) {}

    Point operator + (Point a) { return Point(x+a.x, y+a.y); }
    Point operator - (Point a) { return Point(x-a.x, y-a.y); }
    Point operator * (double k) { return Point(x*k, y*k); }
    Point operator / (double k) { return Point(x/k, y/k); }

    double operator * (Point a) { return x*a.x + y*a.y; } // dot product
    double operator % (Point a) { return x*a.y - y*a.x; } // cross product

    int cmp(Point q) const { if (int t = ::cmp(x,q.x)) return t; return ::cmp(y,q.y); }

    #define Comp(x) bool operator x (Point q) const { return cmp(q) x 0; }
    Comp(>) Comp(<) Comp(==) Comp(>=) Comp(<=) Comp(!=)
    #undef Comp

    Point conj() { return Point(x, -y); }
    double norm() { return x*x + y*y; }

    // Note: There are 2 ways for implementing len():
    // 1. sqrt(norm()) --> fast, but inaccurate (produce some values that are of order X^2)
    // 2. hypot(x, y) --> slow, but much more accurate
    double len() { return sqrt(norm()); }

    Point rotate(double alpha) {
        double cosa = cos(alpha), sina = sin(alpha);
        return Point(x * cosa - y * sina, x * sina + y * cosa);
    }
};

typedef vector<Point> Polygon;

inline int iabs(int x) { if (x < 0) return -x; else return x; }

#define Det(a,b,c) ((double)(b.x-a.x)*(double)(c.y-a.y)-(double)(b.y-a.y)*(c.x-a.x))
bool in_convex(vector<Point>& l, Point p){
    int a = 1, b = l.size()-1, c;
    if (Det(l[0], l[a], l[b]) > 0) swap(a,b);
    if (Det(l[0], l[a], p) >= 0 || Det(l[0], l[b], p) <= 0) return false;
    while(iabs(a-b) > 1) {
        c = (a+b)/2;
        if (Det(l[0], l[c], p) > 0) b = c; else a = c;
    }
    return Det(l[a], l[b], p) < 0;
}

int main() {
    ios :: sync_with_stdio(false); cin.tie(NULL);
    int n;
    while (cin >> n) {
        Polygon a;
        for(int i = 0; i < n; ++i) {
            int x, y; cin >> x >> y;
            a.push_back(Point(x, y));
        }
        int m; cin >> m;
        for(int i = 0; i < m; ++i) {
            int x, y; cin >> x >> y;
            Point P(x, y);

            if (in_convex(a, P)) cout << "YES";
            else cout << "NO";
            cout << "\n";
        }
    }
}

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define oo 1111111111
#define nmax 100111
#define MAX 222

using namespace std;

struct point{
     int x,y;
     bool operator == (point D) const{
          return (x == D.x && y == D.y);       
     }
};

point  a[nmax],p;
int n,m;

long long kc(point a,point b){
      long long X = (b.x-a.x);
      long long Y = (b.y-a.y);
      return X*X+Y*Y;
}

bool behon(point a,point b,point bn){
      long long ax,ay,bx,by;
      ax = a.x - bn.x;
      ay = a.y - bn.y;
      bx = b.x - bn.x;
      by = b.y - bn.y;
      if(ay!=0 && by==0) return true;
      if(ay==0||by==0) return false;
      return ax*by>ay*bx;
}

void Sort(point a[],int l,int r){
      int i = l,j = r;
      point mid = a[(l+r)/2];
      while(i<j){
           while(behon(a[i],mid,a[0])) i++;
           while(behon(mid,a[j],a[0])) j--;
           if(i<=j) swap(a[i++],a[j--]);
      }
      if(i<r) Sort(a,i,r);
      if(l<j) Sort(a,l,j);
}

int ccw(point p1,point p2,point p3){
      long long a1,a2,b1,b2,t;
      a1 = p2.x-p1.x;
      a2 = p3.x-p1.x;
      b1 = p2.y-p1.y;
      b2 = p3.y-p1.y;
      t = a1*b2-a2*b1;
      if(t==0) return 0;
      if(t>0) return 1;
      return -1;
}

int graham(point a[],int n){
      int m = 1;
      for(int i = 2;i<=n;i++)
           if(a[m].y>a[i].y) m = i;
      for(int i = 1;i<=n;i++)
           if(a[i].y==a[m].y && a[i].x>a[m].x) 
                m = i;
      swap(a[1],a[m]);
      a[0].x = a[1].x;
      a[0].y = a[1].y-1;
      Sort(a,2,n);
      a[++n] = a[1];
      m = 2;
      bool ok = true;
      for(int i = 3;i<=n;i++){
             ok = true;
             while(ccw(a[m],a[m-1],a[i])>=0){
                   if(ccw(a[m],a[m-1],a[1])==0){
                        ok = false;
                        if(kc(a[m],a[m-1])<kc(a[m-1],a[i]))
                              swap(a[m],a[i]);
                        break;      
                   }
                   else m--;    
             }
             if(ok) swap(a[++m],a[i]);
      }
      return --m;  
} 

long long stg(point a,point b,point c){
     long long s = (b.x-a.x)*1LL*(b.y+a.y)+(c.x-b.x)*1LL*(c.y+b.y)+ (a.x-c.x)*1LL*(a.y+c.y);
     return s>0?s:-s; 
}

int namtrong(point p,int l,int r,point b[]){
     while(r-l>2){
          int mid = (l+r+1)/2;
          int k = ccw(b[1],b[mid],p);
          if(k==0){
                if((b[1].x-p.x)*(b[mid].x-p.x)<0) return 1;;
                return 0;
          }
          if(k==1) l = mid-1;
          if(k==-1) r = mid;
     }
     point x,y,z;
     x = b[1];
     y = b[r];
     z = b[r-1];
     long long k = stg(x,y,z);
     long long t = stg(x,y,p)+stg(x,z,p)+stg(y,z,p);
     if(t>k) return 0;
     int kk = ccw(x,y,p)*ccw(x,z,p)*ccw(y,z,p);
     if(kk!=0) return 1;
     if(p==x||p==y||p==z) return 0;
     if(r==3){
           if(n<=3) return 0;
           if(ccw(x,y,p)==0)
                 return 1;
     }
     if(r==n &&ccw(x,z,p)==0)
          return 1;
     if(ccw(x,y,p)==0 && r!=n)
           return 1;
     if(ccw(x,z,p)==0 && r!=3)
           return 1;
     return 0;
}

int main(){
     //freopen("METERAIN.in","r",stdin);
     scanf("%d",&n);
     for(int i = 1;i<=n;i++){
          scanf("%d %d",&a[i].x,&a[i].y);
     }   
      // printf("?\n");
     n = graham(a,n);
     //printf("?\n");
     scanf("%d",&m);
     for(int i = 1;i<=m;i++){
          scanf("%d %d",&p.x,&p.y);
          if(namtrong(p,1,n,a)) printf("YES\n");
          else printf("NO\n");
     }
    // getch();
}

Code mẫu của skyvn97

#include<cstdio>
#define MAX   5050
typedef long long ll;
struct point {
    ll x,y;
    point(){}
    point(const ll &_x,const ll &_y) {
        x=_x;y=_y;
    }
    void inp(void) {
        scanf("%lld",&x);
        scanf("%lld",&y);
    }
};
point a[MAX];
point ptl,ptr,pbl,pbr;
int n,m,tl,tr,bl,br;
void init(void) {
    scanf("%d",&n);
    int i;
    for (i=0;i<n;i=i+1) a[i].inp();
    ptl=a[0];ptr=a[0];pbl=a[0];pbr=a[0];
    tl=0;tr=0;bl=0;br=0;
    for (i=1;i<n;i=i+1) {
        if (ptl.x>a[i].x || (ptl.x==a[i].x && ptl.y<a[i].y)) {
            ptl=a[i];
            tl=i;
        }
        if (pbl.x>a[i].x || (pbl.x==a[i].x && pbl.y>a[i].y)) {
            pbl=a[i];
            bl=i;
        }
        if (ptr.x<a[i].x || (ptr.x==a[i].x && ptr.y<a[i].y)) {
            ptr=a[i];
            tr=i;
        }
        if (pbr.x<a[i].x || (pbr.x==a[i].x && pbr.y>a[i].y)) {
            pbr=a[i];
            br=i;
        }
    }   
}
int cmp(const point &a,const point &b,const point &c) { 
    if (a.x>b.x) return (cmp(b,a,c));
    ll left=b.x*a.y-a.x*b.y+c.x*b.y-c.x*a.y;
    ll right=c.y*b.x-c.y*a.x;
    if (left>right) return (1);
    if (left<right) return (-1);
    return (0);
}
int find_bot(const ll &x0) {
    int l,m,r;
    l=(bl+1)%n;
    r=br;
    while (true) {
        if (l==r) return (r);
        if  ((l+1)%n==r) {
            if (a[l].x>=x0) return (l);
            return (r);     
        }
        if (r>l) m=((l+r)/2)%n;
        else m=((l+r+n)/2)%n;
        if (a[m].x>=x0) r=m;
        else l=(m+1)%n;
    }
}
int find_top(const ll &x0) {
    int l,m,r;
    l=tl;
    r=(tr+1)%n;
    while (true) {
        if (l==r) return (l);
        if (l==(r+1)%n) {
            if (a[r].x<=x0) return (r);
            return (l);
        }
        if (l>r) m=((l+r)/2)%n;
        else m=((l+r+n)/2)%n;
        if (a[m].x<=x0) l=m;
        else r=(m+1)%n;
    }
}
bool check(const point &t) {
    if (t.x<=pbl.x) return (false);
    if (t.x>=pbr.x) return (false);
    int ib=find_bot(t.x);
    int it=find_top(t.x);   
    if (cmp(a[ib],a[(ib-1+n)%n],t)>=0) return (false);
    if (cmp(a[it],a[(it-1+n)%n],t)<=0) return (false);
    return (true);
}
void process(void) {
    point t;
    int i;
    scanf("%d",&m);
    for (i=1;i<=m;i=i+1) {      
        t.inp();
        if (check(t)) printf("YES\n");
        else printf("NO\n");
    }
}
int main(void) {
    init();
    process();
    return 0;
}

Code mẫu của khuc_tuan

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;
public class Main {
    class Point {
        public int x,y;
        public Point(int _x,int _y) {
            x=_x; y=_y;
        }
    }
    class Line {
        public Point a,b;
        public Line(int x,int y,int u,int v) {
            if(x<u) {
                a = new Point(x,y);
                b = new Point(u,v);
            }
            else {
                b = new Point(x,y);
                a = new Point(u,v);
            }
        }
    }
    class PointI {
        public int x,y,i;
        public PointI(int _x,int _y,int _i) {
            x=_x; y=_y; i=_i;
        }
    }
    int n,m;
    Line[] dag;
    PointI[] ps;
    int[] result;
    void nhap() throws Exception {
        BufferedReader kb=new BufferedReader(new InputStreamReader(System.in));
        int dx=0,dy=0,tx=0,ty=0;
        boolean ok=false;
        n=parseInt(kb.readLine());
        dag = new Line[n];
        for(int i=0;i<n;++i) {
            StringTokenizer st=new StringTokenizer(kb.readLine());
            int x=parseInt(st.nextToken()), y=parseInt(st.nextToken());
            if(!ok) { dx=x; dy=y; ok=true; }
            else dag[i-1] = new Line(tx,ty,x,y);
            tx=x; ty=y;
        }
        dag[n-1] = new Line(dx,dy,tx,ty);
        m=parseInt(kb.readLine());
        ps=new PointI[m];
        for(int i=0;i<m;++i) {
            StringTokenizer st=new StringTokenizer(kb.readLine());
            int x=parseInt(st.nextToken()), y=parseInt(st.nextToken());
            ps[i]=new PointI(x,y,i);
        }
    }
    void xuly() {
        Arrays.sort(ps,new Comparator<PointI>() {
            public int compare(PointI a, PointI b) {
                return a.x-b.x;
            }
        });
        LinkedList<Line> ts = new LinkedList<Line>();
        for(Line q : dag) ts.add(q);
        Collections.sort(ts, new Comparator<Line>(){
            public int compare(Line a,Line b) {
                return a.a.x-b.a.x;
            }
        });
        LinkedList<Line> ds = new LinkedList<Line>();
        LinkedList<Line> px = new LinkedList<Line>();
        result = new int[m];
        for(int i=0;i<m;++i) {
            while(ts.size()!=0) {
                Line x = ts.getFirst();
                if(x.a.x<=ps[i].x) {
                    ds.add(x);
                    ts.removeFirst();
                }
                else break;
            }
            px.clear();
            for(Line x : ds) if(x.b.x>=ps[i].x) px.add(x);
            ds.clear();
            for(Line x : px) ds.add(x);
            int res=0;
            for(Line q : ds) {
                if(((long)ps[i].y-q.a.y)*(q.b.x-q.a.x)==((long)ps[i].x-q.a.x)*(q.b.y-q.a.y))
                    if(ps[i].x>=q.a.x && ps[i].x<=q.b.x && ps[i].y>=Math.min(q.a.y,q.b.y) && ps[i].y<=Math.max(q.a.y,q.b.y)) {
                        res=0; break;
                    }
                if(q.a.x!=q.b.x) {
                    if(q.a.x==ps[i].x && q.a.y>=ps[i].y) ++res;
                    else if(q.b.x>ps[i].x) {
                        double y = ((double)q.b.y-q.a.y)/(q.b.x-q.a.x)*(ps[i].x-q.a.x) + q.a.y;
                        if(y+1e-8 >= ps[i].y) ++res;
                    }
                }
            }
            result[ps[i].i] = res%2;
        }
        for(int i=0;i<m;++i) System.out.println((result[i]==1)?"YES":"NO");
    }
    void run() throws Exception {
        nhap();
        xuly();
    }
    public static void main(String[] Args) throws Exception {
        new Main().run();
    }
}