Pagini recente » Cod sursa (job #362239) | Cod sursa (job #647332) | Cod sursa (job #778153) | Cod sursa (job #783281) | Cod sursa (job #3266416)
#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)
{
double area = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
if (area < 0)
{
return -1; /// CA is turned clockwise over BA
}
else if (area == 0)
{
return 0; /// CA is colinear with BA
}
else if (area > 0)
{
return 1; /// CA is turned counter clockwise over BA
/// this is what we need here
}
}
double absol(double a)
{
return a < 0 ? -a : a;
}
double triangle_surface(point a, point b, point 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)
{
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)
{
return 2 * triangle_surface(a, b, c) / dist_puncte(a, b);
}
bool cmp(point a, point b)
{
return cross_prod(p[1], a, b) > 0;
}
void convex_hull()
{
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);
// 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 ++;
for (int i = 3; i <= n; i ++)
{
if (cross_prod(stiva[top - 1], stiva[top], p[i]) >= 0 || top < 1)
{
top ++;
stiva.push_back(p[i]);
}
else
{
while (cross_prod(stiva[top - 1], stiva[top], p[i]) == -1)
{
top --;
stiva.pop_back();
}
top ++;
stiva.push_back(p[i]);
}
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> p[i].x >> p[i].y;
p[i].x *= 10;
p[i].y *= 10;
}
convex_hull();
cout << fixed;
/// solutie n^2
double arie_min = 2e9;
for (int i = 0; i < stiva.size(); i ++)
{
// 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 ++)
{
double distanta_perp = dist_dreapta(stiva[i], stiva[(i + 1) % stiva.size()], stiva[j]);
double d_capat1 = dist_puncte(stiva[i], stiva[j]);
double d_capat2 = dist_puncte(stiva[(i + 1) % stiva.size()], stiva[j]);
double d_paralel_capat1 = sqrt(d_capat1 * d_capat1 - distanta_perp * distanta_perp);
double d_paralel_capat2 = sqrt(d_capat2 * d_capat2 - distanta_perp * distanta_perp);
double d1 = dist_puncte(stiva[i], stiva[j]);
double d2 = dist_puncte(stiva[(i + 1) % stiva.size()], stiva[i]);
double d3 = dist_puncte(stiva[(i + 1) % stiva.size()], stiva[j]);
double angle1;
double angle2;
if (d1 == 0)
{
angle2 = 0;
}
else if (d3 == 0)
{
angle1 = 0;
}
else
{
angle1 = (d2 * d2 + d3 * d3 - d1 * d1) / (2 * d2 * d3);
angle2 = (d2 * d2 + d1 * d1 - d3 * d3) / (2 * d2 * d1);
}
if (angle1 < 0 || angle2 < 0)
{
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);
}
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);
}
int rezultat = (double)arie_min;
int zecimale = rezultat % 100;
cout << setprecision(2) << rezultat / 100 << "." << zecimale;
return 0;
}