Pagini recente » Monitorul de evaluare | Cod sursa (job #2910778) | Cod sursa (job #3342525) | Diferente pentru problema/abperm intre reviziile 4 si 3 | Cod sursa (job #3359062)
#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 1ll * (a1.x - a0.x) * (a2.y - a0.y) - 1ll * (a2.x - a0.x) * (a1.y - a0.y);
}
/// ---> convex hull to get relevant points <--- ///
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){
if(crossproduct(a[1], a0, a1) == 0)
return a0 < a1; ///idk if relevant
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;
}
/// ---> no overflow problems <--- ///
int64_t getdistpoints(pii a0, pii a1){
return 1ll * (a0.x - a1.x) * (a0.x - a1.x) + 1ll * (a0.y - a1.y) * (a0.y - a1.y);
}
double getdistpddpoints(pdd a0, pdd a1){
return 1ll * (a0.x - a1.x) * (a0.x - a1.x) + 1ll * (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){
int dxx = a1.x - a0.x, dyy = a1.y - a0.y;
int64_t sumsq = 1ll * dxx * dxx + 1ll * dyy * dyy;
int64_t mintt = 0, maxtt = sumsq;
for(int i = 1; i <= n; i++){
int64_t tt = (1ll * (a[i].x - a0.x) * dxx + 1ll * (a[i].y - a0.y) * dyy);
mintt = min(mintt, tt); maxtt = max(maxtt, tt);
}
return (double)(maxtt - mintt) / sqrt(sumsq);
/**pdd p1 = make_pair(a0.x + (double)mintt / sumsq * dxx, a0.y + (double)mintt / sumsq * dyy);
pdd p2 = make_pair(a0.x + (double)maxtt / sumsq * dxx, a0.y + (double)maxtt / sumsq * dyy);
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];
long 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
long double maxdistfromedge = getmaxdistedge(a[i], a[i + 1], i);
long double maxlengthedge = getlengthedge(a[i], a[i + 1], i);
minarea = min(minarea, maxdistfromedge * maxlengthedge);
}
minarea = (double)(floor(minarea * 100)) / 100;
out<<fixed<<setprecision(2)<<minarea<<"\n";
return 0;
}