自动搬运

查看原文

来自洛谷，原作者为

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

搬运于2025-08-24 21:38:37，当前版本为作者最后更新于2024-12-22 12:14:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

洛谷传送门

动态凸包板子。

思路

删点不好做，考虑离线变成加点。

由于我是从 CF70D 过来的，所以直接改。

然而这里有很多需要注意的地方：

• 同 CF70D，有同横坐标要删掉再加。
• 加入时要把之前相邻两点的长度减掉。
• 离线后要将没有被删过的点加上。

具体细节可以看代码。

代码

#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 ;

struct point 
{
	ll x , y ;
	explicit point ( const ll & x = 0 , const ll & y = 0 ) : x ( x ) , y ( y ) {}
	friend bool operator < ( const point & a , const point & b )
	{
//		if ( a.x == b.x )
//		{
//			return a.y < b.y ;
//		}
		return a.x < b.x ;
	}
};

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

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

ll q ;

ld ans = 0 ;

set <point> up , down ;

bool check_up ( const point & s )
{
	auto it = up.lower_bound ( s ) ;
	if ( it == up.end () )
	{
		return 0 ;
	}
	if ( it -> x == s.x )
	{
		return s.y <= ( it -> y ) ;
	}
	if ( it == up.begin () )
	{
		return 0 ;
	}
	auto it2 = prev ( it ) ;
	return det ( point ( it -> x - it2 -> x , it -> y - it2 -> y ) , point ( s.x - it2 -> x , s.y - it2 -> y ) ) <= 0 ;
}

ld query ()
{
	return ans ;
}

bool remove_up ( const set <point>::iterator it )
{
	if ( it == up.begin () )
	{
		return 0 ;
	}
	auto it2 = it , it3 = it ;
	it2 -- , it3 ++ ;
	if ( it3 == up.end () )
	{
		return 0 ;
	}
	if ( det ( point ( it -> x - it2 -> x , it -> y - it2 -> y ) , point ( it3 -> x - it2 -> x , it3 -> y - it2 -> y ) ) >= 0 )
	{
		// cout << "DEL" << it -> x << " " << it -> y << endl ;
		// cout << ans << " " << dis ( *it2 , *it3 ) << " " << dis ( *it , *it3 ) << " " << dis ( *it , *it2 ) << endl ;
		ans = ans + dis ( *it2 , *it3 ) - dis ( *it , *it2 ) - dis ( *it , *it3 ) ;
		up.erase ( it ) ;
		return 1 ;
	}
	return 0 ;
}

void update_up ( const point & s )
{
	if ( check_up ( s ) )
	{
		return ;
	}
	{
		if ( up.lower_bound ( point ( s.x , -1e9 ) ) != up.upper_bound ( point ( s.x , 1e9 ) ) )
		{
			auto it = up.lower_bound ( point ( s.x , -1e9 ) ) ;
			if ( it != up.begin () )
			{
				ans -= dis ( * prev ( it ) , * it ) ;
			}
			if ( it != prev ( up.end () ) )
			{
				ans -= dis ( * it , * next ( it ) ) ;
			}
			if ( it != up.begin () && it != prev ( up.end () ) )
			{
				ans += dis ( * prev ( it ) , * next ( it ) ) ;
			}
			up.erase ( it ) ;
		}
	}
	auto it = up.insert ( s ).first , it2 = it ;
	if ( it != up.begin () && next ( it ) != up.end () )
	{
		ans -= dis ( * prev ( it ) , * next ( it ) ) ;
	}
	if ( it != up.begin () )
	{
		it2 -- ;
		ans += dis ( * it2 , * it ) ;
		while ( remove_up ( it2 ++ ) ) it2 -- ;
	}
	// cout << "---" << endl ;
	if ( ++ it2 != up.end () )
	{	
		ans += dis ( * it , * it2 ) ;
		while ( remove_up ( it2 -- ) ) ++ it2 ;
	}
}

const ll N = 1e5 + 5 ;

ll n , m ;

point s , p [N] ;

struct node
{
	ll opt ;
	ll u ;
} que [N] ;

ld ansq [N] ;

bool flag [N] ;

int main ()
{
	// freopen ( ".in" , "r" , stdin ) ;
	// freopen ( ".out" , "w" , stdout ) ;
	ios::sync_with_stdio ( 0 ) ;
	cin.tie ( 0 ) ;
	cout.tie ( 0 ) ;
	cin >> n >> s.x >> s.y ;
	cin >> m ;
	for ( ll i = 1 ; i <= m ; i ++ )
	{
		cin >> p [i].x >> p [i].y ;
	}
	update_up ( point ( 0 , 0 ) ) ;
	update_up ( point ( n , 0 ) ) ;
	update_up ( s ) ;
	cin >> q ;
	for ( ll i = 1 ; i <= q ; i ++ )
	{
		cin >> que [i].opt ;
		if ( que [i].opt & 1 )
		{
			cin >> que [i].u ;
			flag [que [i].u] = 1 ;
		}
	}
	for ( ll i = 1 ; i <= m ; i ++ )
	{
		if ( ! flag [i] )
		{
			update_up ( p [i] ) ;
		}
	}
	for ( ll i = q ; i ; i -- )
	{
		if ( que [i].opt & 1 )
		{
			update_up ( p [que [i].u] ) ;
		}
		else
		{
			ansq [i] = query () ;
		}
		// cout << "###" << endl ;
		// for ( auto i : up )
		// {
		// 	cout << i.x << " " << i.y << endl ;
		// }
	}
	for ( ll i = 1 ; i <= q ; i ++ )
	{
		if ( que [i].opt == 2 )
		{
			// cout << ansq [i] << endl ;
			printf ( "%.2Lf\n" , ansq [i] ) ;
		}
	}
	return 0 ;
}