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 flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <utility>
#define fr(a,b,c) for (a=b;a<=c;a++)
#define maxN 10000
using namespace std;

class line
{
    public: double a,b,c;

    public: void create(double x,double y,double xx,double yy)
    {
        a=y-yy; b=xx-x; c=-a*x-b*y;
    }

    public: pair <double,double> intersect(line K)
    {
        double x,y;
        y=(K.a*c-a*K.c)/(K.b*a-b*K.a);
        x=(-c-b*y)/a;
        return make_pair(x,y);
    }
};

class polygon
{
    public: int n,d[maxN];
    double x[maxN],y[maxN];

    public: void add(double xx,double yy)
    {
        x[n]=xx; y[n++]=yy;
    }

    public: void mark(line L,double xp,double yp)
    {
        int i;
        double up=xp*L.a+yp*L.b+L.c;
        fr(i,0,n-1)
        {
            double u=x[i]*L.a+y[i]*L.b+L.c;
            if (u==0) d[i]=0;
            else d[i]=(u*up>=0?1:-1);
        }
    }

    public: polygon cut(line L)
    {
        int i,j;
        polygon b;
        line K;
        pair <double,double> P;
        b.n=0;
        fr(i,0,n-1)
        {
            j=(i+1)%n;
            if (d[i]*d[j]<0) 
            {
                K.create(x[i],y[i],x[j],y[j]);
                P=L.intersect(K);
            }               

            if (d[i]<0)
            {
                if (d[j]>0) b.add(P.first,P.second);
                if (d[j]>=0) b.add(x[j],y[j]);
            }

            if (!d[i])
            {
                if (d[j]>=0) b.add(x[j],y[j]);
            }

            if (d[i]>0)
            {
                if (d[j]>=0) b.add(x[j],y[j]);
                else b.add(P.first,P.second);
            }
        }
        return b;
    }

    public: double area()
    {
        int i;
        double s=0;
        fr(i,0,n-1) s+=(x[i]-x[(i+1)%n])*(y[i]+y[(i+1)%n]);
        s/=2;
        return (s>=0?s:-s);
    }

    public: void debug()
    {
        int i;
        cout << "poly (" << n << ") ";
        fr(i,0,n-1) cout << '(' << x[i] << ',' << y[i] << ") ";
        cout << endl;
    }
};

polygon a;
line b;

int main()
{
    int test,m,re,n;
    double x,y,xx,yy,xp,yp;
    cin >> test;
    while (test--)
    {
        cin >> n;
        a.n=0;
        while (n--)
        {
            scanf("%lf%lf",&x,&y);
            a.add(x,y);
        }
        cin >> xp >> yp >> m;
        while (m--)
        {
            scanf("%lf%lf%lf%lf",&x,&y,&xx,&yy);
            b.create(x,y,xx,yy);
            a.mark(b,xp,yp);
            a=a.cut(b);
        }
        re=int(a.area()*100);
        if (re>a.area()*100) --re;
        printf("%d\n",re);
    }
    return 0;
}

Code mẫu của RR

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cmath>
#include <cstring>

#define FOR(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define REP(i,a) for(int i=0,_a=(a); i < _a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define PR(a,n) {cerr<<#a<<" = "; FOR(_,1,n) cerr << a[_] << ' '; cerr <<endl;}
inline int fastMax(const int &x, const int &y) {return (((y-x)>>(32-1))&(x^y))^y;}
inline int fastMin(const int &x, const int &y) {return (((y-x)>>(32-1))&(x^y))^x;}
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
            if (REACHEOF) return 0;\
            memset(BUF,0,sizeof BUF);\
            int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
            if (inpzzz != BUFSIZE) REACHEOF = true;\
            inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const double EPS = 1e-6; // If integers  should recode every functions with EPS
int cmp(double x, double y) {
    return (x < y+EPS) ? (x > y-EPS) ? 0 : -1 : 1;
}
struct Point {
    double x, y;
    Point(double x = 0, double y = 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; }
};

int ccw(Point a, Point b, Point c) {
    return cmp((b-a)%(c-a),0); 
}
struct Line {
    Point A, B;
    double a, b, c;
    Line(Point A, Point B) : A(A), B(B) {
        a = B.y - A.y;
        b = A.x - B.x;
        c = - (a*A.x + b*A.y);
    }
    double f(Point A) {
        return a*A.x + b*A.y + c;
    }
};

typedef vector< Point > Polygon;

double area(Polygon &p) {
    double s = 0.0;
    FOR(i,1,(int)p.size()-1) s+= (p[i]-p[0])%(p[(i+1)%p.size()]-p[0]);
    return fabs(s) / 2.0;
}

Point crossPoint(Line l, Line m) {
    double A = (l.B - l.A) % (m.B - m.A);
    double B = (l.B - l.A) % (l.B - m.A);
    if (abs(A) < EPS && abs(B) < EPS) return m.A;
    return m.A + (m.B - m.A) * (B / A);
}

Polygon convex_cut(Polygon P, Line l) {
    Polygon Q;
    REP(i,P.size()) {
        Point A = P[i], B = (i == P.size()-1) ? P[0] : P[i+1];
        if (ccw(l.A, l.B, A) != -1) Q.push_back(A);
        if (ccw(l.A, l.B, A)*ccw(l.A, l.B, B) < 0)
                Q.push_back(crossPoint(Line(A, B), l));
    }
    return Q;
}

Polygon P;
Point house;
int n;

int main() {
    ios :: sync_with_stdio(false);
    int ntest; cin >> ntest;
    while (ntest--) {
        cin >> n;
        P.clear();
        FOR(i,1,n) {
            Point cur; cin >> cur.x >> cur.y;
            P.push_back(cur);
        }
        cin >> house.x >> house.y;

        int q; cin >> q;
        while (q--) {
            Point A, B;
            cin >> A.x >> A.y >> B.x >> B.y;
            Line l(A, B);
            if (ccw(A, B, house) == -1) l = Line(B, A);
            P = convex_cut(P, l);
        }
        cout << (int) floor(area(P)*100 + 1e-6) << endl;
    }
}

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>

using namespace std;

typedef long long ll;
typedef double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
//#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }

const int bfsz = 1 << 16;
char bf[bfsz + 5];
int rsz = 0;
int ptr = 0;
char gc() {
    if (rsz <= 0) {
        ptr = 0;
        rsz = (int) fread(bf, 1, bfsz, stdin);
        if (rsz <= 0)
            return EOF;
    }
    --rsz;
    return bf[ptr++];
}
void ga(char &c) {
    c = EOF;
    while (!isalpha(c))
        c = gc();
}
int gs(char s[]) {
    int l = 0;
    char c = gc();
    while (isspace(c))
        c = gc();
    while (c != EOF && !isspace(c)) {
        s[l++] = c;
        c = gc();
    }
    s[l] = '\0';
    return l;
}
template<class T> bool gi(T &v) {
    v = 0;
    char c = gc();
    while (c != EOF && c != '-' && !isdigit(c))
        c = gc();
    if (c == EOF)
        return false;
    bool neg = c == '-';
    if (neg)
        c = gc();
    while (isdigit(c)) {
        v = v * 10 + c - '0';
        c = gc();
    }
    if (neg)
        v = -v;
    return true;
}

typedef pair<int, int> II;

const ld PI = acos(-1.0);
const ld eps = 1e-9;

const int dr[] = {0, +1, 0, -1};
const int dc[] = {+1, 0, -1, 0};

const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const ll mod = (ll)1e9 + 7;

int cmp(ld a, ld b) {
    if (abs(a - b) < eps) return 0;
    return a > b ? 1 : -1;
}

struct Point {
    ld x, y;
    bool operator ==(const Point& that) const {
        return (cmp(x, that.x) == 0 && cmp(y, that.y) == 0);
    }
    bool operator <(const Point& that) const {
        if (cmp(x, that.x) != 0) return cmp(x, that.x) < 0;
        return cmp(y, that.y) < 0;
    }
};

int ccw(Point p0, Point p1, Point p2) {
    ld dx1 = p1.x - p0.x, dy1 = p1.y - p0.y;
    ld dx2 = p2.x - p0.x, dy2 = p2.y - p0.y;
    return cmp(dx1 * dy2 - dx2 * dy1, 0);
}

void getLine(Point p0, Point p1, ld& a, ld& b, ld& c) {
    a = p1.y - p0.y;
    b = p0.x - p1.x;
    c = -(a * p0.x + b * p0.y);
}

int lineIntersect(ld a0, ld b0, ld c0, ld a1, ld b1, ld c1, Point& P) {
    ld d = a0 * b1 - a1 * b0;
    ld dx = b0 * c1 - b1 * c0;
    ld dy = -(c1 * a0 - c0 * a1);
    if (cmp(d, 0) == 0) return (cmp(dx, 0) == 0 && cmp(dy, 0) == 0) ? -1 : 0;
    P.x = dx / d;
    P.y = dy / d;
    return 1;
}


void cutPolygon(Point a[], int &n, Point P, Point Q, Point O) {
    vector<Point> b;

    int co = ccw(O, P, Q);
    ld a1, b1, c1;
    ld a2, b2, c2;
    getLine(P, Q, a1, b1, c1);
    Point I;

    Rep(i, n) {
        int j = (i + 1) % n;
        getLine(a[i], a[j], a2, b2, c2);

        if (ccw(a[i], P, Q) * co < 0) {
            if (ccw(a[j], P, Q) * co > 0) {
                lineIntersect(a1, b1, c1, a2, b2, c2, I);
                b.pb(I);
            }
        } else {
            b.pb(a[i]);
            if (ccw(a[i], P, Q) * co > 0 && ccw(a[j], P, Q) * co < 0) {
                lineIntersect(a1, b1, c1, a2, b2, c2, I);
                b.pb(I);
            }
        }
    }

    n = sz(b);
    Rep(i, n) a[i] = b[i];
}

ld area(Point a[], int n){
    ld res = 0;
    a[n] = a[0];
    Rep(i, n){
        res += a[i].x * a[i + 1].y - a[i].y * a[i + 1].x;
    }
    return abs(res / 2);
}

int n, m;
Point P[100005], A, B, O;
int test;

int  main()
{
//  freopen("in.txt", "r", stdin);

    cin >> test;
    Rep(itest, test){
        cin >> n;
        Rep(i, n) cin >> P[i].x >> P[i].y;
        cin >> O.x >> O.y;
        cin >> m;
        Rep(run, m){
            cin >> A.x >> A.y >> B.x >> B.y;
            cutPolygon(P, n, A, B, O);
        }
        int res = (int)(area(P, n) * 100);
        cout << res << endl;
    }

    return 0;
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <stack>
#include <queue>
#include <utility>
#include <vector>
#define eps 1e-9
using namespace std;

int T,n,Q;
pair<double,double> start;
int sign[1010];

struct line
{
  double a,b,c;
};

line makeLine(pair<double,double> fa,pair<double,double> fb)
{
     line L;
     L.a = fb.second - fa.second;  L.b = fa.first - fb.first;  L.c = -(L.a * fa.first + L.b * fa.second);
     if (L.a < 0)
     {
       L.a = -L.a;  L.b = -L.b;  L.c = -L.c;
     }
     if (abs(L.a) < eps && L.b < 0)
     {
       L.b = -L.b;  L.c = -L.c;
     }
     return L;
 }

pair<double,double> intersect(line L1,line L2)
{
  L1.c = -L1.c;  L2.c = -L2.c;
  double d = L1.a * L2.b - L1.b * L2.a;
  double dx = L1.c * L2.b - L2.c * L1.b;
  double dy = L1.a * L2.c - L2.a * L1.c;
  return make_pair(dx/d,dy/d);
}

double area(vector< pair<double,double> > polygon)
{
  if (polygon.empty()) return 0.0;
  double ans = 0.0; polygon.push_back(polygon[0]);
  for (int i = 0; i + 1 < polygon.size(); i++)
    ans += (polygon[i].first * polygon[i + 1].second - polygon[i + 1].first * polygon[i].second);
  return abs(ans/2.0);
}

vector< pair<double,double> > clipping(vector< pair<double,double> > p,pair<double,double> fa,pair<double,double> fb)
{
  if (p.empty()) return p;
  line L = makeLine(fa,fb);

  p.push_back(p[0]);
  for (int i = 0; i < p.size(); i++)
  {
      double f = L.a * p[i].first + L.b * p[i].second + L.c;
      if (f < 0) sign[i] = -1; else if (f > 0) sign[i] = 1; else sign[i] = 0;      
  }

  vector< pair<double,double> > pos,neg;    
  if (sign[0] <= 0) neg.push_back(p[0]);
  if (sign[0] >= 0) pos.push_back(p[0]);
  for (int i = 1; i < p.size(); i++)
    if (sign[i] * sign[i - 1] > 0)
    {
      if (sign[i] > 0) pos.push_back(p[i]); else neg.push_back(p[i]);
    }
    else if (sign[i] * sign[i - 1] == 0)
    {
         if (sign[i] >= 0) pos.push_back(p[i]);
         if (sign[i] <= 0) neg.push_back(p[i]);
     }
    else
    {
        line T = makeLine(p[i],p[i - 1]);
        pair<double,double> inter = intersect(L,T);
        pos.push_back(inter);  neg.push_back(inter);
        if (sign[i] > 0) pos.push_back(p[i]); else neg.push_back(p[i]);
    }

  if (pos.size() > 1 && pos[0] == pos[pos.size() - 1]) pos.pop_back();
  if (neg.size() > 1 && neg[0] == neg[neg.size() - 1]) neg.pop_back();
  if (start.first * L.a + start.second * L.b + L.c > 0) return pos; else return neg;
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
      scanf("%d", &n);
      vector< pair<double,double> > polygon(n);
      for (int i = 0; i < n; i++) scanf("%lf %lf", &polygon[i].first, &polygon[i].second);
      scanf("%lf %lf", &start.first, &start.second);      
      scanf("%d", &Q);
      for (int i = 0; i < Q; i++)
      {
          pair<double,double> fa,fb;
          scanf("%lf %lf %lf %lf", &fa.first, &fa.second, &fb.first, &fb.second);
          polygon = clipping(polygon,fa,fb);                    
      }
      printf("%d\n", (int) floor(100.0 * area(polygon)) );
    }
}