Previous12345…Next
Username

Prob
	Result 
	Time
(ms)	Mem
(MB)	Lang 
	Submit Time
BrayanD_ADMIN
H
 Judging
C++
5 min ago
BrayanD_ADMIN
H
 Judging
C++
10 min ago
BrayanD_ADMIN
H
Wrong Answer
C++
11 hr ago
BrayanD_ADMIN
H
Wrong Answer
C++
11 hr ago
BrayanD_ADMIN
H
Runtime Error
Bash (GNU bash v4.3.11)
11 hr ago
           
All Copyright Reserved © 2010-2020 Xu Han
Server Time: 2020-03-23 23:04:55 UTC-4

#24921632 | BrayanD_ADMIN's solution for [AtCoder-4778] [Problem H]
Status
Judging 
Length
3948
Lang
C++14 (GCC 5.3.0)
Submitted
2020-03-23 22:59:14
RemoteRunId
11169985
Select Code
#include <bits/stdc++.h>

#define db(x) cerr << #x ": " << (x) << '\n';

#define int long long

using namespace std;

typedef long long ll;

typedef long double ld;

const ld oo = 1e18;

const ld EPS = 1e12;

struct ptt
{
    ld x, y;
    char d;
};

struct point
{
    ld x, y;
    ld vx, vy;
};

int N;

vector<ptt> vect;

ld f(ld m)
{
    ld x1 = oo, y1 = oo, x2 = -oo, y2 = -oo;
    for(int i = 0 ; i < vect.size() ; i++)
    {
        ld x = vect[i].x;
        ld y = vect[i].y;
        char d = vect[i].d;
        if(d == 'U')
        {
            x1 = min(x1,x);
            x2 = max(x2,x);
            y1 = min(y1,y+m);
            y2 = max(y2,y+m);
        }
        if(d == 'R')
        {
            x1 = min(x1,x+m);
            x2 = max(x2,x+m);
            y1 = min(y1,y);
            y2 = max(y2,y);
        }
        if(d == 'D')
        {
            x1 = min(x1,x);
            x2 = max(x2,x);
            y1 = min(y1,y-m);
            y2 = max(y2,y-m);
        }
        if(d == 'L')
        {
            x1 = min(x1,x-m);
            x2 = max(x2,x-m);
            y1 = min(y1,y);
            y2 = max(y2,y);
        }
    }
    return (x2-x1)*(y2-y1);
}

ld ts(ld a, ld b)
{
    for(int i = 0 ; i < 200 ; i++)
    {
        ld m1 = (2.0*a+b)/3.0;
        ld m2 = (a+2.0*b)/3.0;
        if(f(m1) > f(m2))
        {
            a = m1;
        }
        else
        {
            b = m2;
        }
    }
    return f(a);
}

vector<pair<ld,ld>> up;
vector<pair<ld,ld>> rp;
vector<pair<ld,ld>> dp;
vector<pair<ld,ld>> lp;

ld fx(point p1, point p2)
{
    ld a = 0.0, b = 1000000000.0;
    for(int i = 0 ; i < 100 ; i++)
    {
        ld m1 = (2.0*a+b)/3.0;
        ld m2 = (a+2.0*b)/3.0;
        if(fabs(p1.x*p1.vx*m1-p2.x*p2.vx*m1) > fabs(p1.x*p1.vx*m2-p2.x*p2.vx*m2))
        {
            a = m1;
        }
        else
        {
            b = m2;
        }
    }
    return a;
}

ld fy(point p1, point p2)
{
    ld a = 0.0, b = 1000000000.0;
    for(int i = 0 ; i < 100 ; i++)
    {
        ld m1 = (2.0*a+b)/3.0;
        ld m2 = (a+2.0*b)/3.0;
        if(fabs(p1.y*p1.vy*m1-p2.y*p2.vy*m1) > fabs(p1.y*p1.vy*m2-p2.y*p2.vy*m2))
        {
            a = m1;
        }
        else
        {
            b = m2;
        }
    }
    return a;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cout << setprecision(14) << fixed;

    cin >> N;

    for(int i = 0 ; i < N ; i++)
    {
        ld x, y;
        char d;
        cin >> x >> y >> d;
        vect.push_back({x,y,d});
        if(d == 'U')up.push_back({y,x});
        if(d == 'R')rp.push_back({x,y});
        if(d == 'D')dp.push_back({y,x});
        if(d == 'L')lp.push_back({x,y});
    }

    vector<point> vect;

    sort(up.begin(),up.end());
    sort(rp.begin(),rp.end());
    sort(dp.begin(),dp.end());
    sort(lp.begin(),lp.end());

    if(up.size() > 0)vect.push_back({up[0].second,up[0].first,0.0,1.0});
    if(up.size() > 1)vect.push_back({up.back().second,up.back().first,0.0,1.0});

    if(rp.size() > 0)vect.push_back({rp[0].first,rp[0].second,1.0,0.0});
    if(rp.size() > 1)vect.push_back({rp.back().first,rp.back().second,1.0,0.0});

    if(dp.size() > 0)vect.push_back({dp[0].second,dp[0].first,0.0,-1.0});
    if(dp.size() > 1)vect.push_back({dp.back().second,dp.back().first,0.0,-1.0});

    if(lp.size() > 0)vect.push_back({lp[0].first,lp[0].second,-1.0,0.0});
    if(lp.size() > 1)vect.push_back({lp.back().first,lp.back().second,-1.0,0.0});

    vector<ld> pos;

    pos.push_back(0.0);

    for(int i = 0 ; i < vect.size() ; i++)
    {
        for(int j = i+1 ; j < vect.size() ; j++)
        {
            pos.push_back(fx(vect[i],vect[j]));
            pos.push_back(fy(vect[i],vect[j]));
        }
    }

    pos.push_back(1000000005.0);

    ld sol = oo;

    for(int i = 0 ; i < pos.size()-1 ; i++)
    {
        sol = min(sol,ts(pos[i],pos[i+1]));
    }

    cout << sol << '\n';

    return 0;
}