简单凸包0pts求调
查看原帖
简单凸包0pts求调
700210
OIer_Tan楼主2024/12/22 11:05

RT,调了很久调不出来。

代码是用 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 ;
	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 ;
	}
	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] ;

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 ;
		}
	}
	for ( ll i = q ; i ; i -- )
	{
		if ( que [i].opt & 1 )
		{
			update_up ( p [que [i].u] ) ;
		}
		else
		{
			ansq [i] = query () ;
		}
	}
	for ( ll i = 1 ; i <= q ; i ++ )
	{
		if ( que [i].opt == 2 )
		{
			// cout << ansq [i] << endl ;
			printf ( "%.2Lf\n" , ansq [i] ) ;
		}
	}
	return 0 ;
}
2024/12/22 11:05
加载中...