P6719 [BalkanOI2011] 2circles 题解

OIer_Tan · 2024-07-23 16:53:37 · 题解

题目传送门

一道代码量非常大且并不太好想的计算几何。建议评紫。

思路

看到求满足条件的最大值，显然一眼二分。

由于我们要求的是最大的半径，设二分的中间值为 k，考虑将整个凸多边形的边全部往内缩 k 个单位长度，然后可以判断是否有对角线长度大于 2k，有则合法。因为如果有的话，我们可以以这条线段与缩完后凸多边形的交点为圆心放圆，那么如果放在原凸多边形中肯定能放得下。

缩的部分直接用向量缩就好了。然后就上半平面交，求出缩完后所有线段的左手向的半平面的半平面交的交点点集（因为顶点是逆时针给出的）。又因为给定的是凸多边形，所以缩了之后易得也是凸多边形，所以可以直接跑旋转卡壳来求最长的长度。

注意二分边界要加 \text{eps}，否则可能会 T。

代码

#include <bits/stdc++.h>

#ifndef CRT
#define endl '\n'
#endif

using namespace std ;

typedef long long ll ;
typedef unsigned long long ull ;
typedef long double ld ;

const ll N = 5e4 + 5 ;

const ld eps = 1e-6 ;

struct point
{
    ld x , y ;
    explicit point ( const ld & x = 0 , const ld & y = 0 ) : x ( x ) , y ( y ) {}
    friend point operator + ( const point & a , const point & b )
    {
        return point ( a.x + b.x , a.y + b.y ) ;
    } 
    friend point operator - ( const point & a , const point & b )
    {
        return point ( a.x - b.x , a.y - b.y ) ;
    } 
    friend point operator * ( const point & a , const ld & b )
    {
        return point ( a.x * b , a.y * b ) ;
    }
    friend ld operator * ( const point & a , const point & b )
    {
        return a.x * b.x + a.y * b.y ;
    }
} p [N] , pnt [N] ; 

struct vec
{
    point p , v ;
    explicit vec ( const point & a = point () , const point & b = point () ) : p ( a ) , v ( b ) {}
} side [N] , tmp [N] ;

ll n ;

ld cross ( const point & a , const point & b )
{
    return a.x * b.y - b.x * a.y ;
}

ld len ( const point & a )
{
    return sqrt ( a * a ) ;
}

ld dis ( const point & a , const point & b )
{
//  return hypotl ( a.x - b.x , a.y - b.y ) ;
    return len ( a - b ) ;
}

bool direct ( vec l , point p )
{
    return cross ( l.v , p - l.p ) < 0 ;
}

point intersect ( vec a , vec b )
{
    return b.p + b.v * ( cross ( a.v , a.p - b.p ) / cross ( a.v , b.v ) ) ;
}

point perpendicular ( point a )
{
    return point ( a.y , - a.x ) ;
}

point adjust ( point a , ld b )
{
    return point ( a * ( b / len ( a ) ) ) ;
}

vec zoom ( vec p , ld dis )
{
    return vec ( p.p + adjust ( perpendicular ( p.v ) , dis ) , p.v ) ;
}

deque <vec> que ;

bool check ( ld r )
{
    ll j = 1 , m = 0 ;
    ld x , maxn = 0 ;
    for ( ll i = 1 ; i <= n ; i ++ )
    {
        tmp [i] = zoom ( side [i] , -r ) ;
    }
    que.clear () ;
    que.emplace_front ( tmp [1] ) ;
    que.emplace_front ( tmp [2] ) ;
#define bg ( que.begin () )
#define ed prev ( que.end () )
    for ( ll i = 3 ; i <= n ; i ++ )
    {
        while ( que.size () > 1 && 
            direct ( tmp [i] , intersect ( * bg , * next ( bg ) ) ) )
        {
            que.pop_front () ;
        }
        while ( que.size () > 1 && 
            direct ( tmp [i] , intersect ( * ed ,
                * prev ( ed ) ) ) )
        {
            que.pop_back () ;
        }
        que.emplace_front ( tmp [i] ) ;
        while ( que.size () > 2 && 
            direct ( * ed , intersect ( * bg ,
                * next ( bg ) ) ) )
        {
            que.pop_front () ;
        }
        while ( que.size () > 2 && 
            direct ( * bg , intersect ( * ed , 
                * prev ( ed ) ) ) )
        {
            que.pop_back () ;
        }
    }
    for ( auto it = bg ; it != ed ; it ++ )
    {
        pnt [++ m] = intersect ( * it , * next ( it ) ) ;
    }
    if ( bg != ed )
    {
        pnt [++ m] = intersect ( * ed , * bg ) ; 
    }//hpi ed
#undef bg
#undef ed
    for ( ll i = 2 ; i <= m ; i ++ )
    {
        x = dis ( pnt [i] , pnt [1] ) ;
        if ( x >= maxn )
        {
            maxn = x ;
            j = i ;
        }
    }
    if ( maxn >= 2 * r )
    {
        return 1 ;
    }
    for ( ll i = 2 ; i <= m ; i ++ )
    {
        maxn = dis ( pnt [j] , pnt [i] ) ;
        while ( 1 )
        {
            x = dis ( pnt [j % m + 1] , pnt [i] ) ;
            if ( x > maxn )
            {
                maxn = x ;
                j = j % m + 1 ;
            }
            else
            {
                break ;
            }
        }
        if ( maxn >= 2 * r )
        {
            return 1 ;
        }
    }
    return 0 ;
}

int main ()
{
#ifndef CRCC
#ifndef ONLINE_JUDGE
    freopen ( ".in" , "r" , stdin ) ;
    freopen ( ".out" , "w" , stdout ) ;
#endif
#endif
    ios::sync_with_stdio ( 0 ) ;
    cin.tie ( 0 ) ;
    cout.tie ( 0 ) ;
    cin >> n ;
    for ( ll i = 1 ; i <= n ; i ++ )
    {
        cin >> p [i].x >> p [i].y ;
    }
    for ( ll i = 1 , j = 1 ; i <= n ; i ++ )
    {
        j = i % n + 1 ;
        side [i] = vec ( p [i] , p [j] - p [i] ) ;
    }
    ld l = 0 , r = 2e7 ;
    while ( l < r - eps )
    {
        ld mid = ( l + r ) / 2 ;
//      cout << l << " " << r << " " << mid << endl ;
        if ( check ( mid ) ) 
        {
            l = mid ;
        }
        else
        {
            r = mid - 1e-4 ;
        }
    }
    printf ( "%.3Lf" , l ) ;
    return 0 ;
}