Pagini recente » Cod sursa (job #2622401) | Cod sursa (job #953402) | Cod sursa (job #1062911) | Cod sursa (job #1526935) | Cod sursa (job #914015)
Cod sursa(job #914015)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define MAX 100005
#define PII pair<int, int>
#define x first
#define y second
using namespace std;
int N, pct;
int st[MAX * 2], ind[MAX * 2];
bool inStack[MAX];
double parallel, horizontal, ans;
PII V[MAX], aux[MAX];
void citire() {
ifstream in("rubarba.in");
in>>N;
V[0].x = V[0].y = 1000005;
for(int i = 1; i <= N; i++) {
in>>V[i].x>>V[i].y;
if(V[i].x < V[pct].x || (V[i].x == V[pct].x && V[i].y < V[pct].y))
pct = i;
}
in.close();
}
bool cmp(const int &A, const int &B) {
return (1LL * (1LL * (V[A].x - V[pct].x)) * (1LL * (V[B].y - V[pct].y))) <
(1LL * (1LL * (V[B].x - V[pct].x)) * (1LL * (V[A].y - V[pct].y)));
}
inline long long crossProduct(PII O, PII A, PII B) {
return (1LL * (A.x - O.x)) * (1LL * (B.y - O.y)) -
(1LL * (B.x - O.x)) * (1LL * (A.y - O.y));
}
inline long long dotProduct(PII O, PII A, PII B) {
return (1LL * (A.x - O.x)) * (1LL * (B.x - O.x)) +
(1LL * (A.y - O.y)) * (1LL * (B.y - O.y));
}
inline long long dist(const PII &A, const PII &B) {
long long dX = A.x - B.x, dY = A.y - B.y;
return dX * dX + dY * dY;
}
void convexHull() {
for(int i = 1; i <= N; i++)
if(i != pct) ind[++ind[0]] = i;
sort(ind + 1, ind + ind[0] + 1, cmp);
st[st[0] = 1] = pct;
for(int i = 1; i <= ind[0]; i++) {
while(st[0] >= 2 &&
crossProduct(V[st[st[0] - 1]], V[st[st[0]]], V[ind[i]]) >= 0LL)
st[0]--;
st[++st[0]] = ind[i];
}
st[++st[0]] = pct;
for(int i = st[0]; i > 1; i--) aux[i] = V[st[i]];
for(int i = st[0]; i > 1; i--) V[st[0] + 1 - i] = aux[i];
N = st[0] - 1;
}
inline int next(int val) {
if(val == N) return 1;
return val + 1;
}
inline PII getVector(const PII &A, const PII &B) {
PII result;
result.x = B.x - A.x, result.y = B.y - A.y;
return result;
}
double getParallelDistance(const PII &A, const PII &B, const double M) {
return fabs((1.0 * A.y - M * A.x) - (1.0 * B.y - M * B.x)) / sqrt(M * M + 1.0);
}
void getMinimumAreaEnclosingRectangle() {
int i, j = 1, k, m;
PII O;
O.x = O.y = 0;
for(i = 1; i <= N; i++) {
while(dotProduct(O, getVector(V[i], V[next(i)]), getVector(V[j], V[next(j)])) > 0LL)
j = next(j);
if(i == 1) k = j;
while(crossProduct(O, getVector(V[i], V[next(i)]), getVector(V[k], V[next(k)])) > 0LL)
k = next(k);
if(i == 1) m = k;
while(dotProduct(O, getVector(V[i], V[next(i)]), getVector(V[m], V[next(m)])) < 0LL)
m = next(m);
if(V[i].x == V[next(i)].x) {
parallel = fabs(V[k].x - V[i].x);
horizontal = fabs(V[m].y - V[j].y);
} else if(V[i].y == V[next(i)].y) {
parallel = fabs(V[k].y - V[i].y);
horizontal = fabs(V[m].x - V[j].x);
} else {
double slope = (1.0 * (V[next(i)].y - V[i].y)) / (1.0 * (V[next(i)].x - V[i].x));
parallel = getParallelDistance(V[i], V[k], slope);
horizontal = getParallelDistance(V[j], V[m], -1.0 / slope);
}
double area = parallel * horizontal;
if(i == 1 || area < ans)
ans = area;
}
}
void afisare() {
ofstream out("rubarba.out");
out<<fixed<<setprecision(2)<<ans;
}
int main()
{
citire();
if(N > 2) {
convexHull();
getMinimumAreaEnclosingRectangle();
}
afisare();
return 0;
}