Pagini recente » Cod sursa (job #33396) | Cod sursa (job #753235) | Cod sursa (job #1215333) | Cod sursa (job #2290984) | Cod sursa (job #1873122)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
pair <int, int> v[3 * MAXN], aux[MAXN];
inline long long ccw(pair <int, int> A, pair <int, int> B, pair <int, int> C) {
return 1LL * (B.first - A.first) * (C.second - A.second) - 1LL * (B.second - A.second) * (C.first - A.first);
}
bool cmp(pair <int, int> A, pair <int, int> B) {
return ccw(aux[0], A, B) > 0LL;
}
struct Stuff {
double a, b, c;
void init(pair <int, int> X, pair <int, int> Y) {
a = Y.second - X.second;
b = X.first - Y.first;
c = 1LL * X.second * Y.first - 1LL * X.first * Y.second;
double x = sqrt(a * a + b * b);
a /= x;
b /= x;
c /= x;
}
double dist(pair <int, int> P) {
return a * P.first + b * P.second + c;
}
void initp(Stuff d, pair <int, int> P) {
a = -d.b;
b = d.a;
c = -a * P.first - b * P.second;
double x = sqrt(a * a + b * b);
a /= x;
b /= x;
c /= x;
}
} drn, drp;
int main()
{
double area, du, dl, dr, auxd;
int n, st, r, u, l;
ifstream fin("rubarba.in");
fin >> st;
for (int i = 0; i < st; ++i)
fin >> aux[i].first >> aux[i].second;
fin.close();
for (int i = 1; i < st; ++i)
if (aux[i] < aux[0])
swap(aux[i], aux[0]);
sort(aux, aux + st, cmp);
n = 0;
for (int i = 0; i < st; ++i) {
while (n > 1 && ccw(v[n - 2], v[n - 1], aux[i]) < 0LL)
--n;
v[n++] = aux[i];
}
for (int i = 0; i < n; ++i)
v[i + n] = v[i + 2 * n] = v[i];
drn.init(v[n - 1], v[0]);
drp.initp(drn, v[n - 1]);
u = l = 0;
r = n - 1;
du = drn.dist(v[0]);
dl = drp.dist(v[0]);
dr = drp.dist(v[n - 1]);
while ((auxd = drn.dist(v[u + 1])) <= du) {
du = auxd;
++u;
}
while ((auxd = drp.dist(v[l + 1])) >= dl) {
dl = auxd;
++l;
}
while ((auxd = drp.dist(v[r - 1])) <= dr) {
dr = auxd;
--r;
}
area = abs(du) * (dl + abs(dr));
for (int i = 0; i < n - 1; ++i) {
drn.init(v[i], v[i + 1]);
drp.initp(drn, v[i]);
dl = drp.dist(v[l]);
dr = drp.dist(v[r]);
du = drn.dist(v[u]);
while ((auxd = drp.dist(v[l + 1])) >= dl) {
dl = auxd;
++l;
}
while ((auxd = drp.dist(v[r + 1])) <= dr) {
dr = auxd;
++r;
}
while ((auxd = drn.dist(v[u + 1])) <= du) {
du = auxd;
++u;
}
area = min(area, abs(du) * (dl + abs(dr)));
}
ofstream fout("rubarba.out");
fout << setprecision(2) << fixed << area << '\n';
fout.close();
return 0;
}