Cod sursa(job #1097321)

Utilizator danalex97Dan H Alexandru danalex97 Data 3 februarie 2014 12:13:10
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.67 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
using namespace std;

ifstream F("rubarba.in");
ofstream G("rubarba.out");

typedef pair<double,double> pt;
#define x first
#define y second

const int debuging = 0;
const double eps = 0.00000001;

int n;
vector<pt> points,hull;

bool ecu(pt A,pt B,pt C)
{
    int a = A.y - B.y;
    int b = B.x - A.x;
    long long c = - B.x * A.y + A.x * B.y;
    return ( 1LL * a * C.x + 1LL * b * C.y + c ) > 0;
}

vector<pt> parc(vector<pt> a,int l,int r)
{
    int step = l < r ? 1 : -1;
    vector<pt> out;
    for (int i=l;i!=(r+step);i+=step)
        if ( i == l || i == r || ecu(a[l],a[r],a[i]) == 1 )
        {
            out.push_back(a[i]);
            if ( out.size() > 2 )
                while ( ecu(out[int(out.size())-3],out[int(out.size())-1],out[int(out.size())-2]) != 1 )
                {
                    out[int(out.size())-2] = out[int(out.size())-1];
                    out.pop_back();
                    if ( out.size() <= 2 ) break;
                }
        }
    return out;
}

vector<pt> convex_hull(vector<pt> a)
{
    sort(a.begin(),a.end());
    vector<pt> out,stack;
    stack = parc(a,0,n-1);
    for (int i=0;i<int(stack.size())-1;++i)
        out.push_back(stack[i]);
    stack = parc(a,n-1,0);
    for (int i=0;i<int(stack.size())-1;++i)
        out.push_back(stack[i]);
    reverse(out.begin(),out.end());
    return out;
}

void print(vector<pt> a)
{
    if ( !debuging ) return;
    G<<a.size()<<'\n';
    for (size_t i=0;i<a.size();++i)
        G<<a[i].x<<' '<<a[i].y<<'\n';
    G<<'\n';
}

int next(int i)
{
    return (i+1==n) ? 0 : i+1;
}

double dist(pt A,pt B)
{
    return sqrt( 1LL*(A.x-B.x)*(A.x-B.x) +  1LL*(A.y-B.y)*(A.y-B.y) );
}

double dist(pt A,pt B,pt C)
{
    double a = A.y - B.y;
    double b = B.x - A.x;
    double c = - B.x * A.y + A.x * B.y;
    double d = a * C.x + b * C.y + c;
    return ( double(d) / sqrt(a*a+b*b) );
}

pt mid(pt A,pt B)
{
    return make_pair( (A.x + B.x) / 2 , (A.y + B.y) / 2 );
}

void g_ecu(pt A,pt B,double &m,double &n)
{
    m = (B.y - A.y)/(B.x - A.x);
    n = A.y - m * A.x;
}

pt proj(pt A,pt B,pt Q)
{
    if (abs(A.x - B.x) < eps) return make_pair(A.x,Q.y);
    if (abs(A.y - B.y) < eps) return make_pair(Q.x,A.y);
    double m1, n1; g_ecu(A, B, m1, n1);
    double m2 = -1.0 / m1, n2 = Q.y + (1.0 / m1) * Q.x;
    pt out;
    out.x = (n2 - n1) / (m1 - m2);
    out.y = m1 * out.x + n1;
    return out;
}

double rotating_calipers(vector<pt> P)
{
    P.push_back(P.front());
    double ans = double(1LL<<40);
    int l = 0, r = 0;
    for (int i=1;i<n;++i)
    {
        if ( proj(P[0],P[1],P[l]) > proj(P[0],P[1],P[i])) l = i;
        if ( proj(P[0],P[1],P[r]) < proj(P[0],P[1],P[i])) r = i;
    }
    for (int i=0,h=2;i<n;++i)
    {
        while ( next(h) != i && dist(P[i],P[i+1],P[h]) <= dist(P[i],P[i+1],P[next(h)]) + eps ) h = next(h);
        while ((proj(P[i],P[i+1],P[l]) < proj(P[i],P[i+1],P[next(l)])) == (P[i] > P[i+1])) l = next(l);
        while ((proj(P[i],P[i+1],P[r]) < proj(P[i],P[i+1],P[next(r)])) == (P[i] < P[i+1])) r = next(r);
        double d1 = dist(P[i],P[i+1],P[h]);
        double d2 = dist( proj(P[i],P[i+1],P[l]),proj(P[i],P[i+1],P[r]) );
        ans = min(ans,d1*d2);
    }
    return ans;
}

int main()
{
    F>>n;
    for (int i=1,x,y;i<=n;++i)
    {
        F>>x>>y;
        pt ax = make_pair(x,y);
        points.push_back(ax);
    }
    hull = convex_hull(points);
    n = hull.size();
    print(hull);
    double sol = rotating_calipers(hull);
    G<<fixed<<setprecision(2)<<sol<<'\n';
}