Pagini recente » Cod sursa (job #1762089) | Statistici Bosneag Alexandru (AlexBosneag26) | Cod sursa (job #91145) | Cod sursa (job #603546) | Cod sursa (job #3158805)
#include <bits/stdc++.h>
using namespace std;
const int N_MAX = 100000;
using ll = long long;
using d64 = long double;
struct Point {
double x, y;
bool operator<(const Point &oth) const {
if(x == oth.x) {
return y < oth.y;
}
return x < oth.x;
}
};
int N;
vector <Point> P;
int cp(Point a, Point b, Point c) {
ll t = 1ll * (c.y - a.y) * (b.x - a.x) - (b.y - a.y) * (c.x - a.x);
if(t == 0) {
return 0;
}
return t < 0 ? -1 : 1;
}
Point rotate(Point p, double angle) {
return {p.x * cos(angle) - p.y * sin(angle), p.x * sin(angle) + p.y * cos(angle)};
}
vector <Point> convex_hull(vector <Point> P) {
sort(P.begin(), P.end());
vector <Point> ret;
for(int i = 0, t = 1; i >= 0; i += (t = (i == P.size() - 1 ? -t : t))) {
while(ret.size() >= 2 && cp(ret[ret.size() - 2], ret.back(), P[i]) == 1) {
ret.pop_back();
}
ret.push_back(P[i]);
}
return ret;
}
int get_max_x(vector <Point> &C, int index, double angle) {
int ret;
if(index == -1) {
ret = 0;
for(int i = 0; i < C.size() - 1; i++) {
if(rotate(C[ret], angle).x < rotate(C[i], angle).x) {
ret = i;
}
}
}
else {
ret = index;
while(true) {
int i = (ret + 1) % (C.size() - 1);
if(rotate(C[ret], angle).x < rotate(C[i], angle).x) {
ret = i;
}
else {
break;
}
}
}
return ret;
}
int get_min_x(vector <Point> &C, int index, double angle) {
int ret;
if(index == -1) {
ret = 0;
for(int i = 0; i < C.size() - 1; i++) {
if(rotate(C[ret], angle).x > rotate(C[i], angle).x) {
ret = i;
}
}
}
else {
ret = index;
while(true) {
int i = (ret + 1) % (C.size() - 1);
if(rotate(C[ret], angle).x > rotate(C[i], angle).x) {
ret = i;
}
else {
break;
}
}
}
return ret;
}
int get_min_y(vector <Point> &C, int index, double angle) {
int ret;
if(index == -1) {
ret = 0;
for(int i = 0; i < C.size() - 1; i++) {
if(rotate(C[ret], angle).y > rotate(C[i], angle).y) {
ret = i;
}
}
}
else {
ret = index;
while(true) {
int i = (ret + 1) % (C.size() - 1);
if(rotate(C[ret], angle).y > rotate(C[i], angle).y) {
ret = i;
}
else {
break;
}
}
}
return ret;
}
int main() {
#ifndef LOCAL
freopen("rubarba.in", "r", stdin);
freopen("rubarba.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N;
P.resize(N);
for(auto &p : P) {
cin >> p.x >> p.y;
}
if(N <= 2) {
cout << "0\n";
return 0;
}
vector<Point> C = convex_hull(P);
double ans = 1e13;
int max_x = -1, min_x = -1, min_y = -1;
for(int i = 0; i < C.size() - 1; i++) {
double dy = C[i + 1].y - C[i].y;
double dx = C[i + 1].x - C[i].x;
double angle = atan2(dy, dx);
max_x = get_max_x(C, max_x, -angle);
min_x = get_min_x(C, min_x, -angle);
min_y = get_min_y(C, min_y, -angle);
Point a = rotate(C[i], -angle);
Point b = rotate(C[max_x], -angle);
Point c = rotate(C[min_x], -angle);
Point d = rotate(C[min_y], -angle);
ans = min(ans, (a.y - d.y) * (b.x - c.x));
}
long long to_ans = ans * 100;
cout << to_ans / 100 << "." << to_ans % 100 << "\n";
return 0;
}