Problem Description:
You are given N number of coordinates and you have to create a polygon from these points such that they will make a polygon with maximum area.
Note: coordinates provided in the input may or may not be in sequential form.
Constraints
1 <= N <= 10
Input:
First line contains an integer N which depicts number of co-ordinates
Next N lines consist of two space separated integer depicting coordinates of in form of xy
Output:
Print the maximum possible area possible by creating a polygon by joining the coordinates.
If the area is in decimal form, print the absolute value as output.
Time Limit (secs):
1
Examples:
Input:
4
0 0
2 0
0 2
2 2
Output:
4
Explanation:
As we can imagine that these points will make a square shape and the maximum possible area made by the polygon will be 4.
Solution in C :
#include <stdio.h>
#include <stdlib.h>
// Structure to represent a point
struct Point {
int x, y;
};
// Function to compare two points based on x-coordinate (and y-coordinate in case of a tie)
int compare(const void *vp1, const void *vp2) {
struct Point *p1 = (struct Point *)vp1;
struct Point *p2 = (struct Point *)vp2;
// If x-coordinates are different, return the difference
if (p1->x != p2->x)
return (p1->x - p2->x);
// If x-coordinates are the same, return the difference in y-coordinates
return (p1->y - p2->y);
}
// Function to compute the cross product of vectors (p1-p0) and (p2-p0)
int crossProduct(struct Point p0, struct Point p1, struct Point p2) {
int x1 = p1.x - p0.x;
int y1 = p1.y - p0.y;
int x2 = p2.x - p0.x;
int y2 = p2.y - p0.y;
return x1 * y2 - x2 * y1;
}
// Function to find the convex hull using Graham's Scan algorithm
int convexHull(struct Point points[], int n, struct Point *convexHullPoints) {
// If number of points is less than or equal to 3, return all points as the convex hull
if (n <= 3) {
for (int i = 0; i < n; i++)
convexHullPoints[i] = points[i];
return n;
}
// Sort points based on x-coordinate (and y-coordinate in case of a tie)
qsort(points, n, sizeof(struct Point), compare);
// Initialize upper hull and lower hull lists
struct Point upperHull[n], lowerHull[n];
int upperHullSize = 0, lowerHullSize = 0;
// Compute upper hull
for (int i = 0; i < n; i++) {
while (upperHullSize >= 2 && crossProduct(upperHull[upperHullSize - 2], upperHull[upperHullSize - 1], points[i]) <= 0)
upperHullSize--;
upperHull[upperHullSize++] = points[i];
}
// Compute lower hull
for (int i = n - 1; i >= 0; i--) {
while (lowerHullSize >= 2 && crossProduct(lowerHull[lowerHullSize - 2], lowerHull[lowerHullSize - 1], points[i]) <= 0)
lowerHullSize--;
lowerHull[lowerHullSize++] = points[i];
}
// Remove last points from upper hull and lower hull as they will be repeated
upperHullSize--;
lowerHullSize--;
// Merge upper hull and lower hull to get the convex hull
for (int i = 0; i < upperHullSize; i++)
convexHullPoints[i] = upperHull[i];
for (int i = 0; i < lowerHullSize; i++)
convexHullPoints[i + upperHullSize] = lowerHull[i];
// Return the size of convex hull
return upperHullSize + lowerHullSize;
}
// Function to calculate the area of a polygon
long calculateArea(struct Point polygon[], int n) {
// If number of points is less than 3, it's not a valid polygon, return 0
if (n < 3)
return 0;
long area = 0;
// Calculate the area using shoelace formula
for (int i = 0; i < n; i++) {
int x1 = polygon[i].x;
int y1 = polygon[i].y;
int x2 = polygon[(i + 1) % n].x;
int y2 = polygon[(i + 1) % n].y;
area += (x1 * (long)y2 - x2 * (long)y1);
}
// Return the absolute value of area divided by 2
return labs(area) / 2;
}
int main() {
int n;
scanf("%d", &n); // Input the number of points
// Array to store input points
struct Point points[n];
// Input the points
for (int i = 0; i < n; i++)
scanf("%d %d", &points[i].x, &points[i].y);
// Array to store convex hull points
struct Point convexHullPoints[n];
// Compute the convex hull
int convexHullSize = convexHull(points, n, convexHullPoints);
// Calculate the area of convex hull
long maxArea = calculateArea(convexHullPoints, convexHullSize);
// Output the maximum area
printf("%ld\n", maxArea);
return 0;
}
You can also run it on an online IDE:
https://ide.geeksforgeeks.org/online-c-compiler/0ba96fba-85cd-423f-894b-16e875822380
No comments:
Post a Comment