Pagini recente » Cod sursa (job #773518) | Diferente pentru problema/pixeli intre reviziile 4 si 3 | Cod sursa (job #2790776) | Cod sursa (job #2827124) | Cod sursa (job #3357145)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
struct Point {
long long x, y;
bool operator<(const Point& other) const {
if (x != other.x) return x < other.x;
return y < other.y;
}
};
long long crossProduct(const Point& A, const Point& B, const Point& C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
long long dotProduct(const Point& A, const Point& B, const Point& C) {
return (B.x - A.x) * (C.x - A.x) + (B.y - A.y) * (C.y - A.y);
}
vector<Point> getConvexHull(vector<Point>& pts) {
int n = pts.size();
if (n <= 3) return pts;
sort(pts.begin(), pts.end());
vector<Point> hull;
for (int i = 0; i < n; ++i) {
while (hull.size() >= 2 && crossProduct(hull[hull.size() - 2], hull.back(), pts[i]) <= 0) {
hull.pop_back();
}
hull.push_back(pts[i]);
}
size_t lower_size = hull.size();
for (int i = n - 2; i >= 0; --i) {
while (hull.size() > lower_size && crossProduct(hull[hull.size() - 2], hull.back(), pts[i]) <= 0) {
hull.pop_back();
}
hull.push_back(pts[i]);
}
hull.pop_back();
return hull;
}
int main() {
ifstream fin("rubarba.in");
ofstream fout("rubarba.out");
int n;
if (!(fin >> n)) return 0;
vector<Point> pts(n);
for (int i = 0; i < n; ++i) {
fin >> pts[i].x >> pts[i].y;
}
sort(pts.begin(), pts.end());
pts.erase(unique(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
return a.x == b.x && a.y == b.y;
}), pts.end());
vector<Point> hull = getConvexHull(pts);
int h = hull.size();
if (h <= 2) {
fout << "0.00\n";
return 0;
}
double min_area = 1e18;
// Initializam indicii clopotelor
int top = 1, right = 1, left = 1;
for (int i = 0; i < h; ++i) {
Point A = hull[i];
Point B = hull[(i + 1) % h];
long long dx = B.x - A.x;
long long dy = B.y - A.y;
double L2 = dx * dx + dy * dy;
// 1. Inaltimea maxima (Aria paralelogramului sa fie maxima)
while (crossProduct(A, B, hull[(top + 1) % h]) >= crossProduct(A, B, hull[top])) {
top = (top + 1) % h;
}
// 2. Extremitatea dreapta (Proiectia maxima pe directia AB)
while (dotProduct(A, B, hull[(right + 1) % h]) >= dotProduct(A, B, hull[right])) {
right = (right + 1) % h;
}
// 3. Extremitatea stanga (Trebuie sa fie in urma lui right sau resetat la prima rulare)
if (i == 0) left = right;
while (dotProduct(A, B, hull[(left + 1) % h]) <= dotProduct(A, B, hull[left])) {
left = (left + 1) % h;
}
long long height_par = crossProduct(A, B, hull[top]);
long long width_pro = dotProduct(A, B, hull[right]) - dotProduct(A, B, hull[left]);
double current_area = (double)(height_par * width_pro) / L2;
if (current_area < min_area) {
min_area = current_area;
}
}
fout << fixed << setprecision(2) << min_area << "\n";
return 0;
}