Mai intai trebuie sa te autentifici.
Cod sursa(job #1866277)
Utilizator | Data | 2 februarie 2017 20:14:54 | |
---|---|---|---|
Problema | Rubarba | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 3.8 kb |
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#define x first
#define y second
#define DIM 100005
#define eps 0.000000001
using namespace std;
int n, i, u, j, ok;
int s[DIM];
long double aria, sol, xmin, xmax, ymin, ymax, d;
pair<long double, long double> v[DIM], pct, w[DIM];
ifstream fin("rubarba.in");
ofstream fout("rubarba.out");
long double det(long double X1, long double Y1, long double X2, long double Y2, long double X3, long double Y3){
return (X2 - X1) * (Y3 - Y1) - (X3 - X1) * (Y2 - Y1);
}
int cmp(pair<long double, long double> a, pair<long double, long double> b){
double det2 = det(0, 0, a.x, a.y, b.x, b.y);
if(det2 == 0){
return a.x * a.x + a.y * a.y > b.x * b.x + a.y * a.y;
}
return det2 < 0;
}
long double modul(long double x){
if(x > 0){
return x;
}
return -x;
}
pair<long double, long double> pp(pair<long double, long double> d1, pair<long double, long double> d2, pair<long double, long double> p){
if(d1.x == d2.x){
return make_pair(d1.x, p.y);
}
if(d1.y == d2.y){
return make_pair(p.x, d1.y);
}
pair<long double, long double> pct;
long double a1, b1, c1, a2, b2, c2;
a1 = d2.y - d1.y;
b1 = d1.x - d2.x;
c1 = -d1.x * a1 - d1.y * b1;
a2 = -b1;
b2 = a1;
c2 = -p.x * a2 - p.y * b2;
pct.x = (-c1 * b2 + c2 * b1) / (a1 * b2 - a2 * b1);
pct.y = (-c1 - pct.x * a1) / b1;
// double aux = (-c2 - pct.x * a2) / b2;
return pct;
}
int main(){
fin>> n;
v[0].x = v[0].y = 1000000;
for(i = 1; i <= n; i++){
fin>> v[i].x >> v[i].y;
if(v[i].x < v[j].x || (v[i].x == v[j].x && v[i].y < v[j].y)){
j = i;
}
}
swap(v[1], v[j]);
for(i = 2; i <= n; i++){
v[i].x -= v[1].x;
v[i].y -= v[1].y;
}
v[1] = make_pair(0, 0);
sort(v + 2, v + n + 1, cmp);
u = 2;
while(det(v[u - 1].x, v[u - 1].y, v[u].x, v[u].y, v[u + 1].x, v[u + 1].y) == 0){
u++;
}
for(i = 2, j = u; i < j; i++, j--){
swap(v[i], v[j]);
}
s[1] = u = 1;
for(i = 2; i <= n; i++){
while(u >= 2 && det(v[ s[u - 1] ].x, v[ s[u - 1] ].y, v[ s[u] ].x, v[ s[u] ].y, v[i].x, v[i].y) >= 0){
u--;
}
s[++u] = i;
}
for(i = 1; i <= u; i++){
w[i] = v[ s[i] ];
}
w[u + 1] = w[1];
sol = 1000000000000;
for(i = 1; i <= u; i++){
ok = 1;
d = 0;
for(j = 1; j <= u; j++){
if(w[j] != w[i] && w[j] != w[i + 1]){
if(d == 0){
d = det(w[i].x, w[i].y, w[i + 1].x, w[i + 1].y, w[j].x, w[j].y);
}
else{
if(d * det(w[i].x, w[i].y, w[i + 1].x, w[i + 1].y, w[j].x, w[j].y) < 0){
ok = 0;
break;
}
}
}
}
if(ok == 0){
continue;
}
d = 0;
xmin = min(w[i].x, w[i + 1].x);
xmax = max(w[i].x, w[i + 1].x);
ymin = min(w[i].y, w[i + 1].y);
ymax = max(w[i].y, w[i + 1].y);
for(j = 1; j <= u; j++){
if(w[j] != w[i] && w[j] != w[i + 1]){
pct = pp(w[i], w[i + 1], w[j]);
xmin = min(xmin, pct.x);
xmax = max(xmax, pct.x);
ymin = min(ymin, pct.y);
ymax = max(ymax, pct.y);
d = max(d, (pct.x - w[j].x) * (pct.x - w[j].x) + (pct.y - w[j].y) * (pct.y - w[j].y));
}
}
aria = sqrt(d) * sqrt( (xmax - xmin) * (xmax - xmin) + (ymax - ymin) * (ymax - ymin) );
sol = min(sol, aria);
}
fout<< setprecision(2) << fixed << sol <<"\n";
return 0;
}