Cod sursa(job #1786886)

Utilizator Burbon13Burbon13 Burbon13 Data 23 octombrie 2016 20:14:47
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.7 kb
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#define Punct pair<double,double>
#define x first
#define y second

using namespace std;

const int nmx = 100002;
const double error = 0.00000001;

int n, total;
Punct p[nmx], v[3*nmx];
vector <Punct> infs;

void citire()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%lf %lf", &p[i].x, &p[i].second);
}

double determinant(Punct p1, Punct p2, Punct p3)
{
    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}

struct Cmp
{
    bool operator() (Punct p1, Punct p2)
    {
        return determinant(p[1],p1,p2) > 0;
    }
} cmp;

void infasuratoare_convexa()
{
    int pmin = 1;

    for(int i = 2; i <= n; ++i)
        if(p[i] < p[pmin])
            pmin = i;

    swap(p[1],p[pmin]);

    sort(p + 2, p + n + 1, cmp);

    for(int i = 1; i <= n; ++i)
    {
        while(infs.size() >= 2 && determinant(infs[infs.size()-2],infs[infs.size()-1],p[i]) < 0)
            infs.pop_back();
        infs.push_back(p[i]);
    }
}

void copiere_vector()
{
    total = 0;

    for(int t = 0; t < 3; ++t)
    {
        for(vector<Punct>::iterator it = infs.begin(); it != infs.end(); ++it)
            v[++total] = *it;
    }
}

double modul(double val)
{
    return val >= 0 ? val : -val;
}

double dist_punct_punct(Punct p1, Punct p2)
{
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)); /// returneaza patratul
}

double dist_punct_dreapta(Punct p1, double a, double b, double c)
{
    return modul(a * p1.x + b * p1.y + c)  / sqrt(a*a+b*b);
}

void ecuatia_dreptei(Punct p1, Punct p2, double &a, double &b, double &c)
{
    a = p1.y - p2.y;
    b = p2.x - p1.x;
    c = p1.x * p2.y - p2.x * p1.y;
}

double dist_dreapta_triunghi(Punct p1, Punct p2, double a, double b, double c) /// returneaza patratul
{
    double l1,l2;

    l1 = dist_punct_punct(p1,p2);
    l2 = dist_punct_dreapta(p2,a,b,c);

    return sqrt(l1 * l1 - l2 * l2);
}

bool egalitate(double val1, double val2)
{
    return modul(val1-val2) < error;
}

void cautare_extremitati()
{
    int l = infs.size();
    double amax = -1;

    for(int i = l + 1; i <= 2 * l; ++i)
    {
        Punct p1,p2, centru;
        p1 = v[i];
        p2 = v[i+1];
        centru.x = (p1.x + p2.x) / 2;
        centru.y = (p1.y + p2.y) / 2;
        double a,b,c;
        ecuatia_dreptei(p1,p2,a,b,c);

        double dmx1 = 0, dmx2 = 0, dmx3 = 0;

        for(int j = l + 1; j <= 2 * l; ++j)
        {
            double dist1,dist2,dist3;

            dist1 = dist_punct_punct(centru,p2);
            dist2 = dist_dreapta_triunghi(p2,v[j],a,b,c);
            dist3 = dist_dreapta_triunghi(centru,v[j],a,b,c);

            if(egalitate(dist1+dist2,dist3) && dist2 > dmx2)
                dmx2 = dist2;

            dist1 = dist_punct_punct(centru,p1);
            dist2 = dist_dreapta_triunghi(p1,v[j],a,b,c);
            dist3 = dist_dreapta_triunghi(centru,v[j],a,b,c);

            if(egalitate(dist1+dist2,dist3) && dist2 > dmx1)
                dmx1 = dist2;

            dist3 = dist_punct_dreapta(v[j],a,b,c);

            if(dist3 > dmx3)
                dmx3 = dist3;

        }

        double val_aux = (dmx1+dmx2+dist_punct_punct(p1,p2)) * dmx3;

        if(amax == -1)
            amax = val_aux;

        if(amax > val_aux)
            amax = val_aux;
    }

    printf("%.2f\n", amax);
}

int main()
{
    freopen("rubarba.in", "r", stdin);
    freopen("rubarba.out", "w", stdout);
    citire();
    infasuratoare_convexa();
    copiere_vector();
    cautare_extremitati();
    return 0;
}