P2521 [HAOI2011] 防线修建 题解

OIer_Tan · 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 ;
}