Pagini recente » Cod sursa (job #2824564) | Cod sursa (job #2233135) | Cod sursa (job #1461621) | Diferente pentru problema/pscfft intre reviziile 2 si 1 | Cod sursa (job #3357141)
#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;
}
};
// Produsul vectorial (cross product) a doua vectors AB si AC
// > 0 daca C e la stanga lui AB, < 0 daca e la dreapta, 0 daca sunt coliniare
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);
}
// Produsul scalar (dot product) al vectorilor AB si AC
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);
}
// Algoritmul lui Andrew pentru determinarea Invelisului Convex
vector<Point> getConvexHull(vector<Point>& pts) {
int n = pts.size();
if (n <= 3) return pts;
sort(pts.begin(), pts.end());
vector<Point> hull;
// Partea inferioara (Lower 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]);
}
// Partea superioara (Upper hull)
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(); // Ultimul punct coincide cu primul
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;
}
// Eliminam duplicatele daca exista, pentru a nu strica invelisul convex
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) {
// Toate punctele sunt coliniare sau avem prea putine punctele, aria este 0
fout << "0.00\n";
return 0;
}
double min_area = 1e18; // Valoare initiala foarte mare
// Initializam cei 3 indici pentru tehnica Rotating Calipers
int top = 1, right = 1, left = 1;
for (int i = 0; i < h; ++i) {
Point A = hull[i];
Point B = hull[(i + 1) % h];
// Lungimea la patrat a segmentului AB (baza curenta)
long long dx = B.x - A.x;
long long dy = B.y - A.y;
double L2 = dx * dx + dy * dy;
// 1. Gasim punctul cel mai inalt (distanta perpendiculara maxima fata de AB)
// Aria paralelogramului data de crossProduct trebuie sa fie maxima
while (crossProduct(A, B, hull[(top + 1) % h]) >= crossProduct(A, B, hull[top])) {
top = (top + 1) % h;
}
// 2. Gasim punctul cel mai din dreapta (proiectia maxima pe axa AB)
while (dotProduct(A, B, hull[(right + 1) % h]) >= dotProduct(A, B, hull[right])) {
right = (right + 1) % h;
}
// 3. Gasim punctul cel mai din stanga (proiectia minima pe axa AB)
if (i == 0) left = right; // Initializam corect la primul pas
while (dotProduct(A, B, hull[(left + 1) % h]) <= dotProduct(A, B, hull[left])) {
left = (left + 1) % h;
}
// Calculele geometrice folosind produsele scalar / vectorial:
// Inaltimea = Area / sqrt(L2)
// Latimea = (DotProduct_Max - DotProduct_Min) / sqrt(L2)
// Dreptunghiul Area = Inaltime * Latime = (Area_Paralelogram * Latime_Proiectata) / L2
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;
}