Xe duong thang - SutherlandHodgman

#include <stdio.h>
#include <stdlib.h>
#include <stack>
using namespace std;
#define Round(a) (int)(a+0.5)

struct point
{
    int x, y;
};

struct line
{
    point A, B;
    float m;
};

struct rectangle
{
    line AB, BC, CD, DA;
};

stack <point> S;

int check_point(line L, point P)
{
    int c = (L.B.x - L.A.x)*(P.y - L.A.y) - (L.B.y - L.A.y)*(P.x - L.A.x);
    if (c >= 0) return 1;
    else return 0;
}

void check_line(line L, line P1P2)
{
    int a = check_point(L, P1P2.A), b = check_point(L, P1P2.B);
    if (a && b)
    {
        S.push(P1P2.A);
        S.push(P1P2.B);
    }
    else
    {
        point I;
        if (b)
        {
            point temp = P1P2.A;
            P1P2.A = P1P2.B;
            P1P2.B = temp;
        }

        if (L.A.x == L.B.x)
        {
            I.x = L.A.x;
            I.y = P1P2.A.y + Round((float)(I.x - P1P2.A.x)*P1P2.m);
        }
        else if (L.A.y == L.B.y)
        {
            I.y = L.A.y;
            I.x = P1P2.A.x + Round((float)(I.y - P1P2.A.y)/P1P2.m);
        }

        S.push(P1P2.A);
        S.push(I);
    }
}

void SutherlandHodgman(rectangle R, line P1P2)
{
    P1P2.m = (float)(P1P2.B.y - P1P2.A.y)/(P1P2.B.x - P1P2.A.x);

    check_line(R.AB, P1P2);
    P1P2.A = S.top();
    S.pop();
    P1P2.B = S.top();
    S.pop();

    check_line(R.BC, P1P2);
    P1P2.A = S.top();
    S.pop();
    P1P2.B = S.top();
    S.pop();

    check_line(R.CD, P1P2);
    P1P2.A = S.top();
    S.pop();
    P1P2.B = S.top();
    S.pop();
    check_line(R.DA, P1P2);
}

int main()
{
    point A[] = {
            {2,2},  //A
            {8,2},  //B
            {8,6},  //C
            {2,6},  //D
            {1,3},  // P1
            {11,8}  // P2
        };
    line L[] = {
            {A[0], A[1]},   // AB
            {A[1], A[2]},   // BC
            {A[2], A[3]},   // CD
            {A[3], A[0]},   // DA
            {A[4], A[5]},   // P1P2
        };
    rectangle R = {L[0], L[1], L[2], L[3]}; // HCN ABCD
    SutherlandHodgman(R, L[4]);     // Xen P1P2 bang ABCD

    if (S.empty())
    {
        printf("Khong co doan thang nao duoc giu lai");
        return 0;
    }
    printf("Cac doan thang duoc giu lai tao nen tu cac diem:\n");
    while (!S.empty())
    {
        printf("(%d, %d)\n", S.top().x, S.top().y);
        S.pop();
    }

    return 0;
}