Pagini recente » Cod sursa (job #254700) | Cod sursa (job #1200369) | Cod sursa (job #3031193) | Cod sursa (job #614293) | Cod sursa (job #1873081)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
pair <int, int> v[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;
}
} dr, drp;
int main()
{
double area;
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];
}
dr.init(v[n - 1], v[0]);
drp.initp(dr, v[n - 1]);
u = l = 0;
while (dr.dist(v[(u + 1) % n]) < dr.dist(v[u]))
u = (u + 1) % n;
while (drp.dist(v[(l + 1) % n]) > drp.dist(v[l]))
l = (l + 1) % n;
r = n - 1;
while (drp.dist(v[(r + n - 1) % n]) < drp.dist(v[r]))
r = (r + n - 1) % n;
area = abs(dr.dist(v[u])) * (drp.dist(v[l]) + abs(drp.dist(v[r])));
for (int i = 0; i < n - 1; ++i) {
dr.init(v[i], v[i + 1]);
drp.initp(dr, v[i]);
while (drp.dist(v[(l + 1) % n]) > drp.dist(v[l]))
l = (l + 1) % n;
while (drp.dist(v[(r + 1) % n]) < drp.dist(v[r]))
r = (r + 1) % n;
while (dr.dist(v[(u + 1) % n]) < dr.dist(v[u]))
u = (u + 1) % n;
area = min(area, abs(dr.dist(v[u])) * (drp.dist(v[l]) + abs(drp.dist(v[r]))));
}
ofstream fout("rubarba.out");
fout << setprecision(2) << fixed << area << '\n';
fout.close();
return 0;
}