TCS CodeVita Mock Test Coding Question 4

#include<bits/stdc++.h>
using namespace std;
struct Point {
    int x, y;
};
// Comparator function to sort points based on x-coordinate (and y-coordinate in case of a tie)
bool comparePoints(const Point &a, const Point &b) {
    return (a.x < b.x) || (a.x == b.x && a.y < b.y);
}
// Cross product of vectors (p1-p0) and (p2-p0)
int crossProduct(const Point &p0, const Point &p1, const 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;
}
// Graham's Scan algorithm to find the convex hull
vector convexHull(vector &points) {
    int n = points.size();
    if (n <= 3) return points;
    // Sort the points based on x-coordinate (and y-coordinate in case of a tie)
    sort(points.begin(), points.end(), comparePoints);
    // Initialize the upper and lower hulls
    vector upperHull, lowerHull;
    // Build the upper hull
    for (int i = 0; i < n; i++) {
        while (upperHull.size() >= 2 && crossProduct(upperHull[upperHull.size() - 2], upperHull.back(), points[i]) <= 0) {
            upperHull.pop_back();
        }
        upperHull.push_back(points[i]);
    }
    // Build the lower hull
    for (int i = n - 1; i >= 0; i--) {
        while (lowerHull.size() >= 2 && crossProduct(lowerHull[lowerHull.size() - 2], lowerHull.back(), points[i]) <= 0) {
            lowerHull.pop_back();
        }
        lowerHull.push_back(points[i]);
    }
    // Combine the upper and lower hulls to get the convex hull
    upperHull.pop_back(); // Remove the last point to avoid duplication
    lowerHull.pop_back();
    upperHull.insert(upperHull.end(), lowerHull.begin(), lowerHull.end());
    return upperHull;
}
// Calculate the area of a polygon
double calculateArea(vector &polygon) {
    int n = polygon.size();
    if (n < 3) return 0.0; // Not a valid polygon
    double area = 0.0;
    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 * y2 - x2 * y1);
    }
    return abs(area) / 2.0;
}
int main() {
    int n;
    cin >> n;
    vector points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i].x >> points[i].y;
    }
    vector convexHullPoints = convexHull(points);
    double maxArea = calculateArea(convexHullPoints);
    cout << maxArea << endl;
    return 0;
}

// ConvexHull.java

import java.util.*;

class Point {
    int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List points = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            points.add(new Point(x, y));
        }

        List convexHullPoints = convexHull(points);
        long maxArea = calculateArea(convexHullPoints); // Use long to store the result as an integer
        System.out.println(maxArea);
    }

    // Comparator function to sort points based on x-coordinate (and y-coordinate in case of a tie)
    static class PointComparator implements Comparator {
        public int compare(Point a, Point b) {
            if (a.x < b.x || (a.x == b.x && a.y < b.y)) {
                return -1;
            } else if (a.x == b.x && a.y == b.y) {
                return 0;
            } else {
                return 1;
            }
        }
    }

    // Cross product of vectors (p1-p0) and (p2-p0)
    static int crossProduct(Point p0, Point p1, 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;
    }

    // Graham's Scan algorithm to find the convex hull
    static List convexHull(List points) {
        int n = points.size();
        if (n <= 3) return points;

        points.sort(new PointComparator());

        List upperHull = new ArrayList<>();
        List lowerHull = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            while (upperHull.size() >= 2 && crossProduct(upperHull.get(upperHull.size() - 2), upperHull.get(upperHull.size() - 1), points.get(i)) <= 0) {
                upperHull.remove(upperHull.size() - 1);
            }
            upperHull.add(points.get(i));
        }

        for (int i = n - 1; i >= 0; i--) {
            while (lowerHull.size() >= 2 && crossProduct(lowerHull.get(lowerHull.size() - 2), lowerHull.get(lowerHull.size() - 1), points.get(i)) <= 0) {
                lowerHull.remove(lowerHull.size() - 1);
            }
            lowerHull.add(points.get(i));
        }

        upperHull.remove(upperHull.size() - 1);
        lowerHull.remove(lowerHull.size() - 1);

        upperHull.addAll(lowerHull);
        return upperHull;
    }

    // Calculate the area of a polygon and return as an integer
    static long calculateArea(List polygon) {
        int n = polygon.size();
        if (n < 3) return 0; // Not a valid polygon

        long area = 0;

        for (int i = 0; i < n; i++) {
            int x1 = polygon.get(i).x;
            int y1 = polygon.get(i).y;
            int x2 = polygon.get((i + 1) % n).x;
            int y2 = polygon.get((i + 1) % n).y;
            area += (x1 * (long)y2 - x2 * (long)y1); // Use long to avoid overflow
        }

        return Math.abs(area) / 2;
    }
}

import math

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def compare_points(a, b):
    if a.x < b.x or (a.x == b.x and a.y < b.y):
        return -1
    elif a.x == b.x and a.y == b.y:
        return 0
    else:
        return 1

def cross_product(p0, p1, p2):
    x1 = p1.x - p0.x
    y1 = p1.y - p0.y
    x2 = p2.x - p0.x
    y2 = p2.y - p0.y
    return x1 * y2 - x2 * y1

def convex_hull(points):
    n = len(points)
    if n <= 3:
        return points

    points.sort(key=lambda point: (point.x, point.y))

    upper_hull = []
    lower_hull = []

    for i in range(n):
        while len(upper_hull) >= 2 and cross_product(upper_hull[-2], upper_hull[-1], points[i]) <= 0:
            upper_hull.pop()
        upper_hull.append(points[i])

    for i in range(n - 1, -1, -1):
        while len(lower_hull) >= 2 and cross_product(lower_hull[-2], lower_hull[-1], points[i]) <= 0:
            lower_hull.pop()
        lower_hull.append(points[i])

    upper_hull.pop()
    lower_hull.pop()

    upper_hull.extend(lower_hull)
    return upper_hull

def calculate_area(polygon):
    n = len(polygon)
    if n < 3:
        return 0

    area = 0

    for i in range(n):
        x1 = polygon[i].x
        y1 = polygon[i].y
        x2 = polygon[(i + 1) % n].x
        y2 = polygon[(i + 1) % n].y
        area += (x1 * y2 - x2 * y1)

    return abs(area) // 2

if __name__ == "__main__":
    n = int(input())
    points = []

    for _ in range(n):
        x, y = map(int, input().split())
        points.append(Point(x, y))

    convex_hull_points = convex_hull(points)
    max_area = calculate_area(convex_hull_points)
    print(max_area)