自动搬运

查看原文

来自洛谷，原作者为

	OIer_Tan CRT 好玩捏~||前进前进||一点DP都不会||早就不会计算几何了。||CSP2025 RP++

搬运于2025-08-24 22:23:21，当前版本为作者最后更新于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 ;
}