Pagini recente » Cod sursa (job #1730407) | Cod sursa (job #2520581) | Cod sursa (job #1153754) | Cod sursa (job #3336900) | Cod sursa (job #3342089)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
using namespace std;
ifstream cin("rubarba.in");
ofstream cout("rubarba.out");
struct point
{
long long x;
long long y;
};
point p[100001];
vector<point> stiva;
int n;
long long cross_prod(point a, point b, point c) /// produsul vectorial dintre vectorii ab si ac
{
long long 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
{
long long cp = cross_prod(p[1], a, b);
if (cp == 0)
{
return dist_puncte(p[1], a) < dist_puncte(p[1], b);
}
return cp > 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]);
sort(p + 2, p + n + 1, cmp); /// se sorteaza punctele in ordine trigonometrica fata de punctul origine
stiva.push_back(p[1]);
stiva.push_back(p[2]);
/// ne adaugam primele 2 puncte intr-o stiva si aplicam algoritmul graham's scan
for (int i = 3; i <= n; i ++)
{
while (stiva.size() >= 2 && cross_prod(stiva[stiva.size() - 2], stiva[stiva.size() - 1], p[i]) <= 0)
{
stiva.pop_back();
}
stiva.push_back(p[i]);
}
}
void print_convex_hull()
{
for (int i = 0; i < stiva.size(); i ++)
{
cout << stiva[i].x << " " << stiva[i].y << "\n";
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++) /// citim elementele
{
cin >> p[i].x >> p[i].y;
}
if (n == 1)
{
cout << "0.00";
return 0;
}
convex_hull();
print_convex_hull();
cout << fixed << setprecision(2);
/// solutie n^2 pentru problema rubarba
double arie_min = 2e9;
for (int i = 0; i < stiva.size(); i ++)
{
point *A = &stiva[i];
point *B = &stiva[(i + 1) % stiva.size()];
/// componentele vectorului AB
double dx = B->x - A->x;
double dy = B->y - A->y;
double len = sqrt(dx * dx + dy * dy);
double ux = dx / len;
double uy = dy / len;
double rot90_ux = -uy;
double rot90_uy = ux;
double min_proj_C_AB = 2e9;
double max_proj_C_AB = -2e9;
double min_proj_C_rot90_AB = 2e9;
double max_proj_C_rot90_AB = -2e9;
for (int j = 0; j < stiva.size(); j ++)
{
point *C = &stiva[j];
double proj_C_AB = (C->x - A->x) * ux + (C->y - A->y) * uy; /// AC * cos alpha
double proj_C_rot90_AB = (C->x - A->x) * rot90_ux + (C->y - A->y) * rot90_uy; /// AC * cos (90 - alpha) (aka AC * sin alpha)
min_proj_C_AB = min(min_proj_C_AB, proj_C_AB);
max_proj_C_AB = max(max_proj_C_AB, proj_C_AB);
min_proj_C_rot90_AB = min(min_proj_C_rot90_AB, proj_C_rot90_AB);
max_proj_C_rot90_AB = max(max_proj_C_rot90_AB, proj_C_rot90_AB);
}
double lungime = max_proj_C_AB - min_proj_C_AB;
double latime = max_proj_C_rot90_AB - min_proj_C_rot90_AB;
double arie = lungime * latime;
arie_min = min(arie_min, arie);
}
cout << arie_min; /// afisam aria cu 2 zecimale
return 0;
}