Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 months ago
1.6 kB
1
Indexable
Never
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

float find_densest_rectangle(vector<vector<int>>& points) {
    float max_density = -1.0;
    
    for (int i = 0; i < points.size(); ++i) {
        for (int j = i + 1; j < points.size(); ++j) {
            int x1 = points[i][0];
            int y1 = points[i][1];
            int x2 = points[j][0];
            int y2 = points[j][1];
            int width = abs(x2 - x1);
            int height = abs(y2 - y1);
            int area = width * height;
            
            if (area == 0) {
                continue;
            }
            
            int count = 0;
            for (const auto& point : points) {
                int x = point[0];
                int y = point[1];
                if (x1 <= x && x <= x2 && y1 <= y && y <= y2) {
                    count++;
                }
            }
            
            float density = static_cast<float>(count) / area;
            max_density = max(max_density, density);
        }
    }
    
    return max_density != -1.0 ? max_density : -1.0;
}

int main() {
    vector<vector<int>> points1 = {{0, 1}, {0, 10}, {10, 1}, {10, 10}, {2, 3}};
    cout << find_densest_rectangle(points1) << endl;  // Output: 0.011
    
    vector<vector<int>> points2 = {{0, 1}, {0, 10}, {10, 1}, {10, 10}};
    cout << find_densest_rectangle(points2) << endl;  // Output: 0.0
    
    vector<vector<int>> points3 = {{0, 1}, {0, 10}, {10, 1}, {2, 3}};
    cout << find_densest_rectangle(points3) << endl;  // Output: -1.0
    
    return 0;
}
Leave a Comment