Pagini recente » Monitorul de evaluare | Cod sursa (job #1222373) | Cod sursa (job #2724278) | Cod sursa (job #1598189) | Cod sursa (job #3342106)
#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;
double arie_min = 1e18;
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);
return area;
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
}
}
long long dot_prod(point &a, point &b, point &c)
{
long long rez = (b.x - a.x) * (c.x - a.x) + (b.y - a.y) * (c.y - a.y);
return rez;
}
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));
}
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 rotating_calipers()
{
int m = stiva.size();
int top = 1;
int right = 1;
int left = 1;
for (int i = 0; i < m; i ++)
{
point A = stiva[i];
point B = stiva[(i + 1) % m];
long long dx = B.x - A.x;
long long dy = B.y - A.y;
long long len_sq = dx * dx + dy * dy;
while (abs(cross_prod(A, B, stiva[(top + 1) % m])) >= abs(cross_prod(A, B, stiva[top])))
{
top = (top + 1) % m;
}
while (dot_prod(A, B, stiva[(right + 1) % m]) >= dot_prod(A, B, stiva[right]))
{
right = (right + 1) % m;
}
if (i == 0)
{
left = right;
}
while (dot_prod(A, B, stiva[(left + 1) % m]) <= dot_prod(A, B, stiva[left]))
{
left = (left + 1) % m;
}
double height_times_len = abs(cross_prod(A, B, stiva[top]));
double width_times_len = dot_prod(A, B, stiva[right]) - dot_prod(A, B, stiva[left]);
double area = (height_times_len * width_times_len) / (double)len_sq;
arie_min = min(area, arie_min);
}
}
void read()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> p[i].x >> p[i].y;
}
}
void process()
{
convex_hull();
rotating_calipers();
}
void print_result()
{
cout << fixed << setprecision(2);
cout << arie_min;
}
int main()
{
read();
process();
print_result();
return 0;
}