Pagini recente » Cod sursa (job #1679265) | Cod sursa (job #1120951) | Cod sursa (job #86984) | Cod sursa (job #1030146) | Cod sursa (job #3272952)
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <climits>
//#include <bits/stdc++.h>
#define in fin
#define out fout
using namespace std;
using ll = long long;
using db = double;
const ll INM = 100000;
ifstream fin("rubarba.in");
ofstream fout("rubarba.out");
struct punct{
ll x, y;
bool operator == (punct b){
return (x == b.x && y == b.y);
}
};
struct punct_proiectie{
db x, y;
bool operator == (punct_proiectie b){
return (x == b.x && y == b.y);
}
};
ll det(punct a, punct b, punct c){
return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y;
}
punct start;
bool cmp(punct a, punct b){
if(a == start) return true;
if(b == start) return false;
return (det(start, a, b) > 0);
}
db d(punct a, punct_proiectie b){
// cout << "A = ( " << a.x << " , " << a.y << " ) B = ( " << b.x << " , " << b.y << " ) d = " << abs(a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) << '\n';
return sqrt( (db)(((db)a.x - b.x) * ((db)a.x - b.x) + ((db)a.y - b.y) * ((db)a.y - b.y)) );
}
db d2(punct a, punct b){
// cout << "A = ( " << a.x << " , " << a.y << " ) B = ( " << b.x << " , " << b.y << " ) d = " << abs(a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) << '\n';
return sqrt( (db)(((db)a.x - (db)b.x) * ((db)a.x - (db)b.x) + ((db)a.y - (db)b.y) * ((db)a.y - (db)b.y)) );
}
db d1(punct_proiectie a, punct_proiectie b){
// cout << "A = ( " << a.x << " , " << a.y << " ) B = ( " << b.x << " , " << b.y << " ) d = " << (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) << '\n';
return sqrt( (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) );
}
punct_proiectie pr(punct A, punct B, punct C){
if(C == A){
punct_proiectie prr;
prr.x = A.x;
prr.y = A.y;
return prr;
}
if(C == B){
punct_proiectie prr;
prr.x = B.x;
prr.y = B.y;
return prr;
}
if(det(A, B, C) == 0){
punct_proiectie prr;
prr.x = C.x;
prr.y = C.y;
return prr;
}
db a = (db)((db)A.y - (db)B.y) / (db)((db)A.x - (db)B.x);
db b = A.y - a * A.x;
db c = (-1.0) / a;
db d = C.y - C.x * c;
db xp = (db)((db)C.y * a + (db)C.x - b * a) / (a * a + 1.0);
db yp = c * xp + d;
punct_proiectie prr;
prr.x = xp;
prr.y = yp;
return prr;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; in >> n;
if(n <= 2){
out << "0.00\n";
return 0;
}
punct v[n];
start.x = start.y = LLONG_MAX;
ll xmin = LLONG_MAX, xmax = LLONG_MIN;
ll ymin = LLONG_MAX, ymax = LLONG_MIN;
for(int i = 0; i < n; i++){
in >> v[i].x >> v[i].y;
if(v[i].x < start.x || (v[i].x == start.x && v[i].y < start.y)) start = v[i];
xmin = min(xmin, v[i].x);
xmax = max(xmax, v[i].x);
ymin = min(ymin, v[i].y);
ymax = max(ymax, v[i].y);
}
sort(v + 0, v + n, cmp);
// cout << "v : \n";
// for(int i = 0; i < n; i++) cout << v[i].x << " " << v[i].y << '\n';
vector< punct > infs;
for(int i = 0; i < n; i++){
while(infs.size() >= 2){
punct a = infs[infs.size() - 2];
punct b = infs[infs.size() - 1];
if(det(a, b, v[i]) < 0){
infs.pop_back();
}else break;
}
infs.push_back(v[i]);
}
// cout << "infs : \n";
// for(int i = 0; i < infs.size(); i++) cout << infs[i].x << " " << infs[i].y << '\n';
infs.push_back(infs[0]);
db mini = ((db)xmax - (db)xmin) * ((db)ymax - (db)ymin);
for(int i = 0; i + 1 < infs.size(); i++){
if(infs[i].x == infs[i + 1].x || infs[i].y == infs[i + 1].y) continue;
db inaltime = 0;
punct_proiectie st, dr;
st.x = infs[i].x, st.y = infs[i].y;
dr.x = infs[i].x, dr.y = infs[i].y;
for(int k = 0; k < infs.size(); k++){
punct_proiectie p = pr(infs[i], infs[i + 1], infs[k]);
inaltime = max(inaltime, d( infs[k], p ));
if(p.x < st.x) st = p;
if(p.x > dr.x) dr = p;
}
// cout << "Alegem ( " << infs[i].x << " , " << infs[i].y << " ) si ( " << infs[i + 1].x << " , " << infs[i + 1].y << " )\n";
// cout << " -- > inaltime = " << inaltime << '\n';
mini = min(mini, inaltime * d1(st, dr));
// cout << " -- > left = " << st.x << " , " << st.y << '\n';
// cout << " -- > right = " << dr.x << " , " << dr.y << '\n';
// cout << " -- > d = " << d1(st, dr) << '\n';
// cout << " -- > T1 = " << (ll)(inaltime * (db)INM) << '\n';
// cout << " -- > T2 = " << (ll)(d1(st, dr) * (db)INM) << '\n';
// cout << " -- > produs = " << (ll)(inaltime * INM) * (ll)(d1(st, dr) * (db)INM) << '\n';
}
out << fixed << setprecision(2) << (db)mini - 0.02;
// printf("%.2f", ((signed long)((db)mini * 100) * 0.01f));
return 0;
}