#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct {
    float x;
    float y;
} point;

typedef struct {
    point p1;
    point p2;
    point p3;
    point p4;
} rect;


// globally declared counter variable and rect array for storing the final rectangles.
int count = 0;
rect rectArr[1000];


//finding the area of rectangle
float area(rect R) {
    float a = sqrt(pow(R.p2.y - R.p1.y, 2) + pow(R.p2.x - R.p1.x, 2));
    float b = sqrt(pow(R.p3.y - R.p2.y, 2) + pow(R.p3.x - R.p2.x, 2));
    return (a*b);
}


// splitting th rectangles
void split(rect R, rect *R1, rect *R2) {
    float a = sqrt(pow(R.p2.y - R.p1.y, 2) + pow(R.p2.x - R.p1.x, 2));
    float b = sqrt(pow(R.p3.y - R.p2.y, 2) + pow(R.p3.x - R.p2.x, 2));
    point mid1, mid2;
    if(a > b) {
        mid1.x = (R.p1.x + R.p2.x)/2;
        mid1.y = (R.p1.y + R.p2.y)/2;

        mid2.x = (R.p3.x + R.p4.x)/2;
        mid2.y = (R.p3.y + R.p4.y)/2;

        (*R1).p1.x = R.p1.x;
        (*R1).p1.y = R.p1.y;

        (*R1).p2.x = mid1.x;
        (*R1).p2.y = mid1.y;

        (*R1).p3.x = mid2.x;
        (*R1).p3.y = mid2.y;

        (*R1).p4.x = R.p4.x;
        (*R1).p4.y = R.p4.y;


        (*R2).p1.x = mid1.x;
        (*R2).p1.y = mid1.y;

        (*R2).p2.x = R.p2.x;
        (*R2).p2.y = R.p2.y;

        (*R2).p3.x = R.p3.x;
        (*R2).p3.y = R.p3.y;

        (*R2).p4.x = mid2.x;
        (*R2).p4.y = mid2.y;
    }
    else {
        mid1.x = (R.p3.x + R.p2.x)/2;
        mid1.y = (R.p3.y + R.p2.y)/2;

        mid2.x = (R.p1.x + R.p4.x)/2;
        mid2.y = (R.p1.y + R.p4.y)/2;

        (*R1).p1.x = R.p1.x;
        (*R1).p1.y = R.p1.y;

        (*R1).p2.x = R.p2.x;
        (*R1).p2.y = R.p2.y;

        (*R1).p3.x = mid1.x;
        (*R1).p3.y = mid1.y;

        (*R1).p4.x = mid2.x;
        (*R1).p4.y = mid2.y;


        (*R2).p1.x = mid2.x;
        (*R2).p1.y = mid2.y;

        (*R2).p2.x = mid1.x;
        (*R2).p2.y = mid1.y;

        (*R2).p3.x = R.p3.x;
        (*R2).p3.y = R.p3.y;

        (*R2).p4.x = R.p4.x;
        (*R2).p4.y = R.p4.y;
    }
}


// the most important rcursive function of the algorithm
void partition(rect R, float W) {
    if(area(R) <= W) {

        rectArr[count].p1.x = R.p1.x;
        rectArr[count].p1.y = R.p1.y;

        rectArr[count].p2.x = R.p2.x;
        rectArr[count].p2.y = R.p2.y;

        rectArr[count].p3.x = R.p3.x;
        rectArr[count].p3.y = R.p3.y;

        rectArr[count].p4.x = R.p4.x;
        rectArr[count].p4.y = R.p4.y;

        count++;
    }
    else {
        rect R1, R2;
        split(R, &R1, &R2);
        partition(R1, W);
        partition(R2, W);
    }
}


// additinal function to check for the common borders
int isCollinear(point p, point p1, point p2) {
    if(p.x*(p1.y - p2.y) + p1.x*(p2.y - p.y) + p2.x*(p.y - p1.y)) return 0;
    else return 1;
}

int main() {
    rect original;
    float W;
    printf("Please enter the cornwer points of the rectangle in clockwise manner :- \n");
    // for p1:
    printf("Enter the coordinates of p1 : ");
    scanf("%f%f", &original.p1.x, &original.p1.y);
    // for p2:
    printf("Enter the coordinates of p2 : ");
    scanf("%f%f", &original.p2.x, &original.p2.y);
    // for p3:
    printf("Enter the coordinates of p3 : ");
    scanf("%f%f", &original.p3.x, &original.p3.y);
    // for p4:
    printf("Enter the coordinates of p4 : ");
    scanf("%f%f", &original.p4.x, &original.p4.y);

    // for W:
    printf("Enter the value of W : ");
    scanf("%f", &W);

    partition(original, W);
    int j = 1;
    for(int i = 0; i < count; i++) {
        
        // to check if the final rectangles share any border with the original rectangle
        int common = 0;
        if(isCollinear(rectArr[i].p1, original.p1, original.p2) || isCollinear(rectArr[i].p1, original.p2, original.p3) || isCollinear(rectArr[i].p1, original.p3, original.p4) || isCollinear(rectArr[i].p1, original.p4, original.p1))
            common = 1;
        if(isCollinear(rectArr[i].p2, original.p1, original.p2) || isCollinear(rectArr[i].p2, original.p2, original.p3) || isCollinear(rectArr[i].p2, original.p3, original.p4) || isCollinear(rectArr[i].p2, original.p4, original.p1))
            common = 1;
        if(isCollinear(rectArr[i].p3, original.p1, original.p2) || isCollinear(rectArr[i].p3, original.p2, original.p3) || isCollinear(rectArr[i].p3, original.p3, original.p4) || isCollinear(rectArr[i].p3, original.p4, original.p1))
            common = 1;
        if(isCollinear(rectArr[i].p4, original.p1, original.p2) || isCollinear(rectArr[i].p4, original.p2, original.p3) || isCollinear(rectArr[i].p4, original.p3, original.p4) || isCollinear(rectArr[i].p4, original.p4, original.p1))
            common = 1;

        if(common == 1) continue;
        printf("RECT%d : (%f,%f) (%f,%f) (%f,%f) (%f,%f)", j++, rectArr[i].p1.x, rectArr[i].p1.y, rectArr[i].p2.x, rectArr[i].p2.y, rectArr[i].p3.x, rectArr[i].p3.y, rectArr[i].p4.x, rectArr[i].p4.y);
        printf("\n");
    }
    return 0;
}