Mai intai trebuie sa te autentifici.

Cod sursa(job #1866277)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu 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;
}