Pagini recente » Cod sursa (job #2863841) | Cod sursa (job #2182952) | Cod sursa (job #492809) | Borderou de evaluare (job #1800347) | Cod sursa (job #3310262)
#include <ios>
#include <iostream>
#include <fstream>
#include <limits>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
using namespace std;
struct Punct {
double x, y;
Punct operator-(const Punct &p) const {
return {x - p.x, y - p.y};
}
Punct operator+(const Punct &p) const {
return {x + p.x, y + p.y};
}
Punct operator*(double t) const {
return {x * t, y * t};
}
double operator^(const Punct &p) const {
return x*p.y - y*p.x;
}
};
vector<Punct> infasuratoare(vector<Punct> poligon) {
map<double, Punct> p;
int imn;
Punct mn{10e12, 10e12};
for(int i=0; i<poligon.size(); ++i) {
auto &punct = poligon[i];
if(punct.y < mn.y || (punct.y == mn.y && punct.x < mn.x)) {
mn = punct;
imn = i;
}
}
for(int i=0; i<poligon.size(); ++i) {
auto &punct = poligon[i];
if(imn != i) {
double unghi = atan2(punct.y-mn.y, punct.x-mn.x);
if(!p.count(unghi)) {
p[unghi] = punct;
} else {
double d1 = (p[unghi].x-mn.x)*(p[unghi].x-mn.x) + (p[unghi].y-mn.y)*(p[unghi].y-mn.y);
double d2 = (punct.x-mn.x)*(punct.x-mn.x) + (punct.y-mn.y)*(punct.y-mn.y);
if(d2 > d1) {
p[unghi] = punct;
}
}
}
}
vector<Punct> stiva;
stiva.push_back(mn);
for(auto &[unghi, punct] : p) {
while(stiva.size() >= 2) {
Punct A = stiva[stiva.size()-2];
Punct B = stiva[stiva.size()-1];
long double k = (B.x - A.x)*(punct.y - A.y) - (B.y - A.y)*(punct.x - A.x);
if(k <= 0) {
stiva.pop_back();
} else {
break;
}
}
stiva.push_back(punct);
}
return stiva;
}
double lungime(Punct A, Punct B) {
return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}
double ariaHeron(double AB, double AC, double BC) {
double s = (AB+AC+BC)/2;
return sqrt(s*(s-AB)*(s-BC)*(s-AC));
}
double distantaPunctDreapta(Punct P, Punct A, Punct B) {
double AB = lungime(A, B);
double AP = lungime(A, P);
double BP = lungime(B, P);
double aria = ariaHeron(AB, AP, BP);
return 2 * aria / AB;
}
double distantaProiectie(Punct P, Punct A, Punct B) {
double lg = lungime(A, B);
if(!lg) {
return 0;
}
return ((P.x-A.x) * (B.x-A.x) + (P.y-A.y) * (B.y-A.y)) / lg;
}
double dreptunghi(vector<Punct> infasuratoare) {
double mn = numeric_limits<double>::max();
int N = infasuratoare.size();
for(int i=0; i<N; ++i) {
Punct A = infasuratoare[i];
Punct B = infasuratoare[(i+1)%N];
double dmx = 0;
for(int j=0; j<N; ++j) {
double distanta = distantaPunctDreapta(infasuratoare[j], A, B);
if(distanta > dmx) {
dmx = distanta;
}
//cout << "h " << dmx << '\n';
}
double stmx = numeric_limits<double>::max(), drmx = -numeric_limits<double>::max();
for(int j=0; j<N; ++j) {
double proiectie = distantaProiectie(infasuratoare[j], A, B);
stmx = min(proiectie, stmx);
drmx = max(proiectie, drmx);
//cout << "! " << stmx << ' ' << drmx << '\n';
}
//cout << "!! " << dmx * (drmx-stmx) << '\n';
mn = min(mn, dmx * (drmx-stmx));
}
return mn;
}
int main() {
ifstream fin("rubarba.in");
ofstream fout("rubarba.out");
fout << fixed << setprecision(2);
int N;
fin >> N;
vector<Punct> pt(N);
for(int i=0; i<N; ++i) {
fin >> pt[i].x >> pt[i].y;
}
auto cpt = infasuratoare(pt);
fout << dreptunghi(cpt) << '\n';
return 0;
}