Pagini recente » Cod sursa (job #1727271) | Cod sursa (job #2036586) | Cod sursa (job #2477725) | Cod sursa (job #2593424) | Cod sursa (job #911352)
Cod sursa(job #911352)
#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;
int st[MAX];
bool inStack[MAX];
double parallel, horizontal, ans;
PII V[MAX], aux[MAX];
void citire() {
ifstream in("rubarba.in");
in>>N;
for(int i = 1; i <= N; i++) in>>V[i].x>>V[i].y;
in.close();
}
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));
}
void convexHull() {
sort(V + 1, V + N + 1);
st[++st[0]] = 1, st[++st[0]] = 2;
inStack[2] = true;
for(int i = 1, p = 1; i > 0; i += (p = (i == N ? -p : p))) {
if(inStack[i]) continue;
while(st[0] >= 2 && crossProduct(V[st[st[0] - 1]], V[st[st[0]]], V[i]) <= 0LL)
inStack[st[st[0]--]] = false;
st[++st[0]] = i;
inStack[i] = true;
}
for(N = 1; N < st[0]; N++) aux[N] = V[st[N]];
N--;
for(int i = 1; i <= N; i++) V[i] = aux[i];
}
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 = abs(V[k].x - V[i].x);
horizontal = abs(V[m].y - V[j].y);
} else if(V[i].y == V[next(i)].y) {
parallel = abs(V[k].y - V[i].y);
horizontal = abs(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();
convexHull();
getMinimumAreaEnclosingRectangle();
afisare();
return 0;
}