Cod sursa(job #1088669)

Utilizator MyrmekoMeMarin Cristian MyrmekoMe Data 20 ianuarie 2014 18:52:20
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 7.31 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#define NMax 100010
#define limit 1000000
#define Next ++position == limit?f.read(buffer, limit), position = 0:0
#define ch buffer[position]
#define EPS 1e-9
#define INF 2000000000
#define fINF 1e15

using namespace std;

double ans = fINF;
int st[NMax];
ifstream f ("rubarba.in");
int position;
char buffer[limit];
int n;
struct punct
{
    int x, y;
    punct ()
    {
        x = y = 0;
    }
    punct (const int _x, const int _y)
    {
        x = _x;
        y = _y;
    }
};
punct a[2*NMax];

inline void Read(int &x)
{
    for (; ch < '0' || ch > '9'; Next);
    for (x = 0; '0' <= ch && ch <= '9'; x = x*10 + ch - '0', Next);
}

void Read()
{
    f.read(buffer, limit);
    Read(n);
    int pos = 1;
    for (int i=1; i<=n; ++i)
    {
        int x, y;
        Read(x), Read(y);
        a[i] = punct(x, y);
        if (y < a[pos].y || (y == a[pos].y && x < a[pos].x))
            pos = i;
    }
    f.close();
    swap(a[1], a[pos]);
}

inline long long sqr(const int x)
{
    return 1LL * x * x;
}

inline double fsqr(const double x)
{
    return x * x;
}

inline double Dist(const punct &A, const punct &B)
{
    return sqrt(1.0*(sqr(A.x-B.x)+sqr(A.y-B.y)));
}

inline bool cmp(const punct &A, const punct &B)
{
    long long p1, p2;
    p1 = 1LL*(A.y - a[1].y)*(B.x - a[1].x);
    p2 = 1LL*(B.y - a[1].y)*(A.x - a[1].x);
    if (p1 == p2)
        return (Dist(A, a[1]) < Dist(B, a[1]));
    return p1 < p2;
}

inline long long Det(const punct &A, const punct &B, const punct &C)
{
    // A.x A.y 1
    // B.x B.y 1
    // C.x C.y 1
    return 1LL*A.x*B.y + 1LL*A.y*C.x + 1LL*B.x*C.y - 1LL*B.y*C.x - 1LL*A.x*C.y - 1LL*B.x*A.y;
}

void ConvexHull()
{
    sort(a+2, a+n+1, cmp);
    int vf, i;
    long long o;
    vf = 0;
    st[++vf] = 1;
    st[++vf] = 2;
    for (i = 3; i<=n; ++i)
    {
        o = Det(a[st[vf-1]], a[st[vf]], a[i]);
        if (o == 0)
            st[vf] = i;
        else
            if (o > 0)
                st[++vf] = i;
            else
            {
                while (vf >= 2 && o < 0)
                {
                    --vf;
                    o = Det(a[st[vf-1]], a[st[vf]], a[i]);
                }
                st[++vf] = i;
            }
    }

    for (i=1; i<=vf; ++i)
        a[i] = a[st[i]];

    n = vf + vf;
    for (; i<=n; ++i)
        a[i] = a[i-vf];
}

inline double DistP_dr(const punct &pct, const int &A, const int &B, const long long &C)
{
    return fabs(1.0*(1LL*A*pct.x + 1LL*B*pct.y + C)) / sqrt(1.0*(sqr(A) + sqr(B)));
}

inline double Distanta_in_dreapta(const int ind1, const int ind2, const double dist12, const int ind, const int coefa, const int coefb, const long long coefc)
{
    double _aux, _aux2, d, dd;
    _aux = DistP_dr(a[ind], coefa, coefb, coefc);
    _aux2 = Dist(a[ind], a[ind2]);
    d = sqrt(fsqr(_aux2) - fsqr(_aux));
    dd = sqrt(fsqr(Dist(a[ind], a[ind1])) - fsqr(_aux));
    if (fabs(dd - d - dist12) <= EPS)
        return d;
    return -1.0;
}

inline double Distanta_in_stanga(const int ind1, const int ind2, const double dist12, const int ind, const int coefa, const int coefb, const long long coefc)
{
    double _aux, _aux2, d, dd;
    _aux = DistP_dr(a[ind], coefa, coefb, coefc);
    _aux2 = Dist(a[ind], a[ind1]);
    d = sqrt(fsqr(_aux2) - fsqr(_aux));
    dd = sqrt(fsqr(Dist(a[ind], a[ind2])) - fsqr(_aux));
    if (fabs(dd - d - dist12) <= EPS)
        return d;
    return -1.0;
}

inline double AreaDreptunghi(const int ind1, const int ind2, const double dist12, const int sus, const int stanga, const int dreapta, const int coefa, const int coefb, const long long coefc)
{
    double x = DistP_dr(a[sus], coefa, coefb, coefc);
    double y = dist12 + Distanta_in_dreapta(ind1, ind2, dist12, dreapta, coefa, coefb, coefc) + Distanta_in_stanga(ind1, ind2, dist12, stanga, coefa, coefb, coefc);
    return x * y;
}

void Solve()
{
    ConvexHull();
    int i, sus = 1, stanga, dreapta;
    stanga = 1;
    dreapta = 2;
    double distmaxsus, distmaxstanga, distmaxdreapta;
    double dist12 = Dist(a[1], a[2]);
    int coefa, coefb;
    long long coefc;
    distmaxdreapta = distmaxstanga = distmaxsus = -1.0;
    coefa = a[1].y - a[2].y;
    coefb = a[2].x - a[1].x;
    coefc = 1LL*a[1].x*a[2].y - 1LL*a[1].y*a[2].x;
    //cout<<coefa<<" "<<coefb<<" "<<coefc<<"\n";
    int n2 = n/2;
    for (i = 3; i<= n2; ++i)
    {
        double _aux = DistP_dr(a[i], coefa, coefb, coefc);
        if (_aux > distmaxsus || fabs(distmaxsus - _aux) <= EPS)
        {
            distmaxsus = _aux;
            sus = i;
        }
    }

    for (i=3; i<=n2; ++i)
    {
        double d = Distanta_in_dreapta(1, 2, dist12, i, coefa, coefb, coefc);
        if (d != -1.0 && (d > distmaxdreapta || fabs(d - distmaxdreapta) <= EPS))
        {
            distmaxdreapta = d;
            dreapta = i;
        }
    }

    for (i=3; i<=n2; ++i)
    {
        double d = Distanta_in_stanga(1, 2, dist12, i, coefa, coefb, coefc);
        if (d != -1.0 && (d > distmaxstanga || fabs(d-distmaxstanga) <= EPS))
        {
            distmaxstanga = d;
            stanga = i;
        }
    }
    if (stanga == 1)
        stanga = n / 2 + 1;
    ans = min(ans, AreaDreptunghi(1, 2, dist12, sus, stanga, dreapta, coefa, coefb, coefc));
    int lim = n / 2;
    for (i=2; i<=lim; ++i)
    {
        /// fixez latura i, i+1

        coefa = a[i].y - a[i+1].y;
        coefb = a[i+1].x - a[i].x;
        coefc = 1LL*a[i].x*a[i+1].y - 1LL*a[i].y*a[i+1].x;
        dist12 = Dist(a[i], a[i+1]);
        double d, dnow;

        dnow = DistP_dr(a[sus], coefa, coefb, coefc);
        d = DistP_dr(a[sus+1], coefa, coefb, coefc);
        while (sus < n && d > dnow)
        {
            dnow = d;
            ++sus;
            d = DistP_dr(a[sus+1], coefa, coefb, coefc);
        }

        ///
        if (dreapta == i)
            ++dreapta;
        dnow = Distanta_in_dreapta(i, i+1, dist12, dreapta, coefa, coefb, coefc);
        d = Distanta_in_dreapta(i, i+1, dist12, dreapta+1, coefa, coefb, coefc);
        while (dreapta < n && d != -1.0 && d > dnow)
        {
            dnow = d;
            ++dreapta;
            d = Distanta_in_dreapta(i, i+1, dist12, dreapta+1, coefa, coefb, coefc);
        }
        ///
        if (a[stanga].x == a[i+1].x && a[stanga].y == a[i+1].y )/// ciuriburi
            ++stanga;
        dnow = Distanta_in_stanga(i, i+1, dist12, stanga, coefa, coefb, coefc);
        while (stanga < n && dnow == -1.0)
        {
            ++stanga;
            dnow = Distanta_in_stanga(i, i+1, dist12, stanga, coefa, coefb, coefc);
        }
        d = Distanta_in_stanga(i, i+1, dist12, stanga+1, coefa, coefb, coefc);
        while (stanga < n && d != -1.0 && d > dnow)
        {
            dnow = d;
            ++stanga;
            d = Distanta_in_stanga(i, i+1, dist12, stanga+1, coefa, coefb, coefc);
        }

        ans = min(ans, AreaDreptunghi(i, i+1, dist12, sus, stanga, dreapta, coefa, coefb, coefc));
    }
    //cout<<ans;
}

void Write()
{
    FILE *g = fopen ("rubarba.out", "w");
    fprintf(g, "%.2lf\n", ans);
    fclose(g);
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}