Pagini recente » Cod sursa (job #2942419) | Cod sursa (job #927965) | Cod sursa (job #1384663) | Cod sursa (job #566333) | Cod sursa (job #3266780)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
using namespace std;
ifstream cin("rubarba.in");
ofstream cout("rubarba.out");
struct point
{
double x;
double y;
};
point p[100001];
vector<point> stiva;
int n;
int cross_prod(point a, point b, point c) /// produsul vectorial dintre vectorii ab si ac
{
double area = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
if (area < 0)
{
return -1; /// C este rotit mai mult in sensul acelor de ceasornic decat B fata de punctul A
}
else if (area == 0)
{
return 0; /// punctele A, B, C sunt coliniare
}
else if (area > 0)
{
return 1; /// C este rotit mai mult in sens trigonometric decat B fata de punctul A
/// ne trebuie asta pentru functia cmp()
}
}
double absol(double a) /// functie valoare absoluta (in modul)
{
return a < 0 ? -a : a;
}
double triangle_surface(point a, point b, point c) /// calcularea ariei triunghiului determinat de punctele a, b, c
{
return 0.5 * absol(a.x * b.y + c.x * a.y + b.x * c.y - b.y * c.x - c.y * a.x - b.x * a.y);
}
double dist_puncte(point a, point b) /// calcularea distantei dintre punctele a, b
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double dist_dreapta(point a, point b, point c) /// calcularea distantei de la punctul c la dreapta ab
{
return 2 * triangle_surface(a, b, c) / dist_puncte(a, b);
}
bool cmp(point a, point b) /// functie de comparare pentru sort() pentru sortarea punctelor in ordine trigonometrica
{
return cross_prod(p[1], a, b) > 0;
}
void convex_hull() /// algoritmul "graham's scan" pentru determinarea infasuratorii convexe in O(n * log n)
{
int minpos = 1;
for (int i = 1; i <= n; i ++)
{
if (p[minpos].y > p[i].y)
{
minpos = i;
}
else if (p[minpos].y == p[i].y)
{
if (p[minpos].x > p[i].x)
{
minpos = i;
}
}
}
swap(p[minpos], p[1]); /// punctul cel mai de jos, (respectiv cel mai din stanga in caz de egalitate), este pus pe prima pozitie a sirului de puncte
/// acesta va fi punctul origine
sort(p + 2, p + n + 1, cmp); /// se sorteaza punctele in ordine trigonometrica fata de punctul origine
// for (int i = 1; i <= n; i ++)
// {
// cout << p[i].x << " " << p[i].y << "\n";
// }
int top = 0;
stiva.push_back(p[1]);
stiva.push_back(p[2]);
top ++;
/// ne adaugam primele 2 puncte intr-o stiva si aplicam algoritmul graham's scan
for (int i = 3; i <= n; i ++)
{
/// daca gasim un punct rotit mai mult in sens trigonometric decat ultimul punct din stiva fata de penultimul punct din stiva
if (cross_prod(stiva[top - 1], stiva[top], p[i]) >= 0 || top < 1)
{
top ++;
stiva.push_back(p[i]); /// atunci adaugam elementul
}
else /// daca nu, eliminam ultimele puncte din stiva cat timp nu respecta conditia
{
while (cross_prod(stiva[top - 1], stiva[top], p[i]) == -1)
{
top --;
stiva.pop_back();
}
top ++;
stiva.push_back(p[i]); /// adaugam la sfarsit elementul curent
}
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++) /// citim elementele
{
cin >> p[i].x >> p[i].y;
}
if (n == 1) /// caz separat pentru n = 1 (fara el, se afiseaza -0.00)
{
cout << "0.00";
return 0;
}
convex_hull();
cout << fixed;
/// solutie n^2 pentru problema rubarba
double arie_min = 2e9;
for (int i = 0; i < stiva.size(); i ++) /// pentru fiecare 2 puncte adiacente de pe infasuratoare (care determina un segment AB)
{
// cout << stiva[i].x << " " << stiva[i].y << "\n";
// cout << stiva[(i + 1) % stiva.size()].x << " " << stiva[(i + 1) % stiva.size()].y << "\n\n";
double d_paralel_capat1_max = -1;
double d_paralel_capat2_max = -1;
double d_perp_max = -1;
for (int j = 0; j < stiva.size(); j ++) /// parcurgem restul punctelor (fie acestea C) si calculam:
{
double d1 = dist_puncte(stiva[i], stiva[j]); /// distanta de la C la A
double d2 = dist_puncte(stiva[(i + 1) % stiva.size()], stiva[i]); /// distanta de la A la B (segmentul AB)
double d3 = dist_puncte(stiva[(i + 1) % stiva.size()], stiva[j]); /// distanta de la C la B
double distanta_perp = dist_dreapta(stiva[i], stiva[(i + 1) % stiva.size()], stiva[j]); /// distanta de la C la segmentul AB
double d_capat1 = d1; /// distanta de la C la A (din nou)
double d_capat2 = d3; /// distanta de la C la B (din nou)
double d_paralel_capat1 = sqrt(d_capat1 * d_capat1 - distanta_perp * distanta_perp); /// lungimea proiectiei segmentului CA pe dreapta AB
double d_paralel_capat2 = sqrt(d_capat2 * d_capat2 - distanta_perp * distanta_perp); /// lungimea proiectiei segmentului CB pe dreapta AB
double angle1;
double angle2;
if (d1 == 0) /// cazuri pentru cand punctul C coincide cu A sau B, pentru a evita o impartire la 0
{
angle2 = 0;
}
else if (d3 == 0)
{
angle1 = 0;
}
else
{
angle1 = (d2 * d2 + d3 * d3 - d1 * d1) / (2 * d2 * d3); /// formula pentru calcularea cosinusului unghiului ABC
angle2 = (d2 * d2 + d1 * d1 - d3 * d3) / (2 * d2 * d1); /// formula pentru calcularea cosinusului unghiului BAC
/// facem asta pentru a vedea daca proiectia punctului C pe dreapta AB se afla si pe segmentul AB
}
if (angle1 <= 0 || angle2 <= 0) /// cosinusul unui unghi obtuz este mai mare sau egal cu 0 (egalitatea se atinge pentru un unghi de 90 de grade)
{
/// vrem sa calculam cele mai indepartate puncte din stanga segmentului AB, respectiv din dreapta segmentului AB
/// pentru a determina lungimea dreptunghiului construit
if (d_paralel_capat1 < d_paralel_capat2)
{
d_paralel_capat1_max = max(d_paralel_capat1, d_paralel_capat1_max);
}
else
{
d_paralel_capat2_max = max(d_paralel_capat2, d_paralel_capat2_max);
}
}
d_perp_max = max(d_perp_max, distanta_perp); /// calculeaza cea mai mare distanta perpendiculara pe AB (latimea dreptunghiului)
}
double arie = (dist_puncte(stiva[i], stiva[(i + 1) % stiva.size()]) + d_paralel_capat1_max + d_paralel_capat2_max) * d_perp_max;
arie_min = min(arie, arie_min); /// calculam aria
}
cout << setprecision(2) << arie_min; /// afisam aria cu 2 zecimale
return 0;
}