Cod sursa(job #1350152)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 20 februarie 2015 18:06:11
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.58 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream in("rubarba.in");
ofstream out("rubarba.out");
 
struct point
{
   int x,y;
};

const int nmax = 100006;
int n, k; 
double a, b, c;
long double area = 1000000000000;
point v[nmax], st[nmax];

double modul(double x)
{
	if(x<0)
		return -x;
	else
		return x;
}

long long det (point a, point b, point c)
{
    return (long long)(b.x - a.x)*(long long)(c.y - a.y) - (long long)(c.x - a.x) * (long long)(b.y - a.y);
}
 
bool cmp(point a, point b)
{
    return det(v[1], a, b)>0;
}
 
double dist(point p)
{
    return modul(a * p.x + b * p.y + c) / sqrt(a * a + b * b);
} 
 
double line_dist_short(point p)
{
    return modul(a*p.x + b*p.y + c);
}
 
int bs (int lo, int hi)
{
    if (hi<lo)
        return 0;
 
    int inlo = lo, inhi = hi, mid;
    double val;
 
    while (1)
    {
        mid = (lo + hi)/2;
 
        double lval, rval;
 
        val = line_dist_short (st[mid]);
 
        if (mid!=inlo)
            lval = line_dist_short (st[mid - 1]);
        if (mid!=inhi)
            rval = line_dist_short (st[mid + 1]);
 
        if ((mid==inlo || lval<=val) && (mid==inhi || val>=rval))
          break;
 
        if (mid>inlo && lval>val)
            hi = mid - 1;
        else 
			lo = mid + 1;
    }
 
    return mid;
}
 
int main()
{
	int player_unu=0;

	out<<setprecision(2)<<fixed;

    in>>n;
 
    int mini = 1;
 
    for(int i = 1; i<=n; i++)
    {
        in>>v[i].x>>v[i].y;
 
        if(v[i].x<v[mini].x || (v[i].x==v[mini].x && v[i].y<v[mini].y))
            mini = i;
    }
 
    swap(v[1], v[mini]);
    sort(v + 2, v + n + 1, cmp);
 
    k = 0;
    for (int i = 1; i<=n; i++)
    {
        while (k>=2 && det(st[k - 1], st[k], v[i])<=0)
            --k;

		k++;
        st[k] = v[i];
    }
 
    for(int i = 1; i<k; i++)
    {
        a = st[i + 1].y - st[i].y;
        b = st[i].x - st[i + 1].x;
        c = (long long)st[i].y * (long long)st[i+1].x - (long long)st[i].x*(long long)st[i+1].y;
 
        int dr1 = bs(1, i);
        double d1 = dist(st[dr1]);
 
        int dr2 = bs (i + 1, k);
        double d2 = dist(st[dr2]);
 
        int dr;
        if(d1>d2)
             dr = dr1;
        else
			dr = dr2;
 
        if(a!=0)
        {
            double m = b / a;
            a = m;
            b = -1;
            c = -m * st[dr].x + st[dr].y;
        }
 
        if(d1>d2)
        {
            int l = bs(dr1, i);
 
            int r1 = bs (1, dr1);
            int r2 = bs (i + 1, k);
 
 
            double chestie = max (dist(st[r1]), dist(st[r2])) + dist(st[l]);
 
            area = min (area,(long double)d1 * chestie);
        }
        else
        {
            int r = bs (i + 1, dr2);
 
            int l1 = bs (1, i);
            int l2 = bs (dr2, k);
 
            double chestie = max (dist(st[l1]), dist(st[l2])) + dist(st[r]);
 
            area = min (area, (long double)d2 * chestie);
        }
    }
 
 
    a = st[k].y - st[1].y;
    b = st[1].x - st[k].x;
    c = (long long)st[1].y * (long long)st[k].x - (long long)st[1].x * (long long)st[k].y;
 
    int dr = bs (1, k);
    double d = dist(st[dr]);
 
    if(a!=0)
    {
        double m = b / a;
        a = m;
        b = -1;
        c = -m * st[dr].x + st[dr].y;
    }
 
    int l = bs (1, dr);
    int r = bs (dr, k);
 
    double chestie = dist(st[l]) + dist(st[r]);
 
    area = min(area, (long double)d * chestie);
 
    out<<area;

	return player_unu;
}