Untitled

 avatar
unknown
plain_text
5 months ago
6.9 kB
4
Indexable
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <functional> // Included for std::function

using namespace std;

struct Point
{
    double x, y;
    int id; // for vertex identification

    Point(double x = 0, double y = 0, int id = -1) : x(x), y(y), id(id) {}

    bool operator<(const Point &other) const
    {
        if (fabs(x - other.x) > 1e-9)
            return x < other.x;
        return y < other.y;
    }

    bool operator==(const Point &other) const
    {
        return fabs(x - other.x) < 1e-9 && fabs(y - other.y) < 1e-9;
    }
};

struct Segment
{
    Point p1, p2;
};

int N;
vector<Point> points;
vector<Segment> segments;
map<pair<int, int>, vector<int>> adj; // adjacency list

double cross(const Point &O, const Point &A, const Point &B)
{
    // Cross product (OA x OB)
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

bool onSegment(const Point &p, const Point &q, const Point &r)
{
    // Check if point q lies on segment pr
    return q.x <= max(p.x, r.x) + 1e-9 && q.x >= min(p.x, r.x) - 1e-9 &&
           q.y <= max(p.y, r.y) + 1e-9 && q.y >= min(p.y, r.y) - 1e-9;
}

bool segmentsIntersect(Point p1, Point q1, Point p2, Point q2)
{
    // Check if segments p1q1 and p2q2 intersect
    double o1 = cross(p1, q1, p2);
    double o2 = cross(p1, q1, q2);
    double o3 = cross(p2, q2, p1);
    double o4 = cross(p2, q2, q1);

    if (o1 * o2 < -1e-9 && o3 * o4 < -1e-9)
        return true;

    // Colinear cases
    if (fabs(o1) < 1e-9 && onSegment(p1, p2, q1))
        return true;
    if (fabs(o2) < 1e-9 && onSegment(p1, q2, q1))
        return true;
    if (fabs(o3) < 1e-9 && onSegment(p2, p1, q2))
        return true;
    if (fabs(o4) < 1e-9 && onSegment(p2, q1, q2))
        return true;

    return false;
}

Point getIntersection(Point p1, Point p2, Point p3, Point p4)
{
    // Return intersection point of lines p1p2 and p3p4
    // Assume they intersect
    double A1 = p2.y - p1.y;
    double B1 = p1.x - p2.x;
    double C1 = A1 * p1.x + B1 * p1.y;

    double A2 = p4.y - p3.y;
    double B2 = p3.x - p4.x;
    double C2 = A2 * p3.x + B2 * p3.y;

    double det = A1 * B2 - A2 * B1;
    if (fabs(det) < 1e-9)
    {
        // Lines are parallel (should not happen if they intersect)
        return Point();
    }
    else
    {
        double x = (B2 * C1 - B1 * C2) / det;
        double y = (A1 * C2 - A2 * C1) / det;
        return Point(x, y);
    }
}

int main()
{
    cin >> N;

    // Read segments
    int point_id = 0;
    map<Point, int> point_ids;
    for (int i = 0; i < N; ++i)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        Point p1(x1, y1), p2(x2, y2);

        if (point_ids.find(p1) == point_ids.end())
        {
            p1.id = point_id;
            point_ids[p1] = point_id++;
            points.push_back(p1);
        }
        else
        {
            p1.id = point_ids[p1];
        }

        if (point_ids.find(p2) == point_ids.end())
        {
            p2.id = point_id;
            point_ids[p2] = point_id++;
            points.push_back(p2);
        }
        else
        {
            p2.id = point_ids[p2];
        }

        segments.push_back({p1, p2});
    }

    // Find all intersection points
    for (size_t i = 0; i < segments.size(); ++i)
    {
        for (size_t j = i + 1; j < segments.size(); ++j)
        {
            if (segmentsIntersect(segments[i].p1, segments[i].p2, segments[j].p1, segments[j].p2))
            {
                Point ip = getIntersection(segments[i].p1, segments[i].p2, segments[j].p1, segments[j].p2);
                if (point_ids.find(ip) == point_ids.end())
                {
                    ip.id = point_id;
                    point_ids[ip] = point_id++;
points.push_back(ip);
                }
                else
                {
                    ip.id = point_ids[ip];
                }
            }
        }
    }
    map<int, vector<int>> adjList;
    for (auto &seg : segments)
    {
        vector<Point> pts_on_seg;
        for (auto &pt : points)
        {
            // Check if pt lies on segment
            if (onSegment(seg.p1, pt, seg.p2) && fabs(cross(seg.p1, seg.p2, pt)) < 1e-9)
            {
                pts_on_seg.push_back(pt);
            }
        }

        // Sort points along the segment
        sort(pts_on_seg.begin(), pts_on_seg.end(), [&](const Point &a, const Point &b)
             {
            double da = hypot(a.x - seg.p1.x, a.y - seg.p1.y);
            double db = hypot(b.x - seg.p1.x, b.y - seg.p1.y);
            return da < db; });

        // Create edges between consecutive points
        for (size_t i = 0; i < pts_on_seg.size() - 1; ++i)
        {
            int u = pts_on_seg[i].id;
            int v = pts_on_seg[i + 1].id;
            if (u != v)
            {
                adjList[u].push_back(v);
                adjList[v].push_back(u);
            }
        }
    }

    // Now, find all cycles (faces) in the planar graph
    set<vector<int>> cycles;
    int maxArea = 0;

    // Function to find all simple cycles starting from a node
    function<void(int, int, vector<int> &, set<int> &)> dfs =
        [&](int start, int u, vector<int> &path, set<int> &visited)
    {
        visited.insert(u);
        path.push_back(u);

        for (int v : adjList[u])
        {
            if (v == start && path.size() >= 3)
            {
                // Found a cycle
                vector<int> cycle = path;
                // Normalize the cycle for uniqueness
                int min_idx = min_element(cycle.begin(), cycle.end()) - cycle.begin();
                rotate(cycle.begin(), cycle.begin() + min_idx, cycle.end());
                if (cross(points[cycle[0]], points[cycle[1]], points[cycle[2]]) < 0)
                {
                    reverse(cycle.begin(), cycle.end());
                }
                cycles.insert(cycle);
            }
            else if (visited.find(v) == visited.end())
            {
                dfs(start, v, path, visited);
            }
        }
        visited.erase(u);
        path.pop_back();
    };

    // Start DFS from each node
    for (size_t i = 0; i < points.size(); ++i)
    {
        vector<int> path;
        set<int> visited;
        dfs(i, i, path, visited);
    }

    // For each cycle, compute area
    for (auto &cycle : cycles)
    {
        double area = 0;
        int sz = cycle.size();
        for (int i = 0; i < sz; ++i)
        {
            Point &p1 = points[cycle[i]];
            Point &p2 = points[cycle[(i + 1) % sz]];
            area += (p1.x * p2.y - p2.x * p1.y);
        }
        area = fabs(area) / 2.0;
        maxArea = max(maxArea, static_cast<int>(area + 0.5)); // Round to nearest integer
    }

    cout << maxArea;

    return 0;
}


Editor is loading...
Leave a Comment