Pagini recente » Cod sursa (job #2182616) | Cod sursa (job #1284654) | Monitorul de evaluare | Cod sursa (job #3318046) | Cod sursa (job #3359022)
#include <fstream>
#include <utility>
#define x first
#define y second
#include <algorithm>
#include <iomanip>
#include <cstdint>
#include <cmath>
using namespace std;
ifstream in("rubarba.in");
ofstream out("rubarba.out");
typedef pair <int, int> pii;
typedef pair <double, double> pdd;
const int nmax = 1e5;
int n; pii a[nmax + 2];
int64_t crossproduct(pii a0, pii a1, pii a2){
return (a1.x - a0.x) * (a2.y - a0.y) - (a2.x - a0.x) * (a1.y - a0.y);
}
pii stk[nmax + 2]; int stktopp;
void getconvexhull(){
for(int i = 2; i <= n; i++){
if(a[1] > a[i]){
swap(a[1], a[i]);
}
}
sort(a + 2, a + 1 + n, [](pii a0, pii a1){
return (crossproduct(a[1], a0, a1) < 0);
});
stk[++stktopp] = a[1];
stk[++stktopp] = a[2];
for(int i = 3; i <= n; i++){
for(; stktopp >= 2 && crossproduct(stk[stktopp - 1], stk[stktopp], a[i]) >= 0; stktopp--);
stk[++stktopp] = a[i];
}
for(n = 0; stktopp >= 1; stktopp--){
a[++n] = stk[stktopp];
}
return;
}
int64_t getdistpoints(pii a0, pii a1){
return (a0.x - a1.x) * (a0.x - a1.x) + (a0.y - a1.y) * (a0.y - a1.y);
}
double getdistpddpoints(pdd a0, pdd a1){
return (a0.x - a1.x) * (a0.x - a1.x) + (a0.y - a1.y) * (a0.y - a1.y);
}
int myabs(int xx){ return ((xx < 0) ? -xx : xx); }
int64_t myabs(int64_t xx){ return ((xx < 0) ? -xx : xx); }
double getmaxdistedge(pii a0, pii a1, int idx){
double lengthbase = sqrt(getdistpoints(a0, a1));
int64_t maxarea = 0; ///we only need the maximum one :)
for(int i = 1; i <= n; i++){
maxarea = max(maxarea, myabs(crossproduct(a0, a1, a[i])));
}
return ((double)maxarea / lengthbase);
}
double getlengthedge(pii a0, pii a1, int idx){
double edgelength = sqrt(getdistpoints(a0, a1));
pdd p1 = a0, p2 = a1; ///we can compute these points very easily
int dxx = a1.x - a0.x, dyy = a1.y - a0.y;
int sumsq = dxx * dxx + dyy * dyy;
for(int i = 1; i <= n; i++){
double tt = (double)((a[i].x - a0.x) * dxx + (a[i].y - a0.y) * dyy) / (double)(sumsq);
pdd pointt = make_pair(a0.x + tt * dxx, a0.y + tt * dyy);
if(tt < 0 && getdistpddpoints(a0, p1) < getdistpddpoints(a0, pointt)){ p1 = pointt; }
if(tt > 1 && getdistpddpoints(a1, p2) < getdistpddpoints(a1, pointt)){ p2 = pointt; }
}
return sqrt(getdistpddpoints(p1, p2));
}
int main(){
in>>n; if(n == 1){ out<<"0.00\n"; return 0; }
for(int i = 1; i <= n; i++){
in>>a[i].x>>a[i].y;
}
getconvexhull();
a[n + 1] = a[1];
double minarea = 1e18;
for(int i = 1; i <= n; i++){
///we choose an edge to be (a[i], a[i + 1])
///we know the dist * base = |cross product|
///so that means we need to compute the minimum area for this
double maxdistfromedge = getmaxdistedge(a[i], a[i + 1], i);
double maxlengthedge = getlengthedge(a[i], a[i + 1], i);
minarea = min(minarea, maxdistfromedge * maxlengthedge);
}
minarea = (double)((int)(minarea * 100)) / 100;
out<<fixed<<setprecision(2)<<minarea<<"\n";
return 0;
}