【HAOI2011 Day1】防线修建

时间限制 : 10000 MS 空间限制 : 565536 KB

问题描述

近来A国和B国的矛盾激化，为了预防不测，A国准备修建一条长长的防线，当然修建防线的话，肯定要把需要保护的城市修在防线内部了。可是A国上层现在还犹豫不决，到底该把哪些城市作为保护对象呢？又由于A国的经费有限，所以希望你能帮忙完成如下的一个任务：
1. 给出你所有的A国城市坐标
2. A国上层经过讨论，考虑到经济问题，决定取消对i城市的保护，也就是说i城市不需要在防线内了
3. A国上层询问对于剩下要保护的城市，修建防线的总经费最少是多少
你需要对每次询问作出回答。注意单位1长度的防线花费为1。
A国的地形是这样的，形如下图，x轴是一条河流，相当于一条天然防线，不需要你再修建A国总是有两个城市在河边，一个点是(0,0)，一个点是(n,0)，其余所有点的横坐标均大于0小于n，纵坐标均大于0。A国有一个不在(0,0)和(n,0)的首都。(0,0),(n,0)和首都这三个城市是一定需要保护的。

上图中，A,B,C,D,E点为A国城市，且目前都要保护，那么修建的防线就会是A-B-C-D，花费也就是线段AB的长度+线段BC的长度+线段CD的长度。
如果，这个时候撤销B点的保护，那么防线变成下图

输入格式

第一行，三个整数n,x,y分别表示河边城市和首都是(0,0)，(n,0)，(x,y)。 第二行，一个整数m。
接下来m行，每行两个整数a,b表示A国的一个非首都非河边城市的坐标为(a,b)。 再接下来一个整数q，表示修改和询问总数。
接下来q行每行要么形如1 i，要么形如2，分别表示撤销第i个城市的保护和询问。

输出格式

对于每个询问输出1行，一个实数v，表示修建防线的花费，保留两位小数

样例输入

4 2 1
2
1 2
3 2
5
2
1 1
2
1 2
2

样例输出

6.47
5.84
4.47

提示

数据范围： 30%的数据m<=1000,q<=1000
100%的数据m<=100000,q<=200000,n>1
所有点的坐标范围均在10000以内, 数据保证没有重点

题解

本题修防线的最优情况显然是在凸包上，由于有删点操作，我们需要维护一个动态凸包。本题在凸包上删点的过程十分麻烦，且没有强制在线，因此我们可以考虑离线倒序操作，化删除操作为更加方便的添加操作。
至于维护一个动态凸包，我们可以把凸包（分上下凸壳，本题只有上凸壳）中的所有点放入一棵平衡树中（其实用set就可以了），每次操作时不断查找当前点的前驱和后继来维护凸性质即可（十分暴力）。

代码

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<set>
using namespace std;
typedef double db;
const int maxn=1e5+5;
int n,m,cnt;
db sum,ans[2*maxn];
bool flag[maxn];
struct Point{
    db x,y;
    Point(){}
    Point(db x,db y):x(x),y(y){}
}p[maxn];
typedef Point Vector;
struct query{
    int op,t;
}q[2*maxn];
set<Point> s;
set<Point>::iterator las,pre,temp;
bool operator < (const Point& a,const Point& b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
Vector operator - (const Point& a,const Point& b)
{
    return Vector(a.x-b.x,a.y-b.y);
}
db Cross(Vector a,Vector b)
{
    return a.x*b.y-a.y*b.x;
}
db Dot(Vector a,Vector b)
{
    return a.x*b.x+a.y*b.y;
}
db Length(Vector a)
{
    return sqrt(Dot(a,a));
}
void Insert(int a)
{
    las=s.upper_bound(p[a]),pre=las,las--;
    if(Cross(*las-*pre,p[a]-*pre)>=0) return;
    sum-=Length(*las-*pre);
    while(true)
    {
        temp=pre,pre++;
        if(pre==s.end()) break;
        if(Cross(*temp-*pre,p[a]-*pre)>=0) break;
        sum-=Length(*temp-*pre),s.erase(temp);
    }
    while(true)
    {
        if(las==s.begin()) break;
        temp=las,las--;
        if(Cross(*temp-*las,p[a]-*las)<=0) break;
        sum-=Length(*temp-*las),s.erase(temp);
    }
    s.insert(p[a]);
    las=pre=s.find(p[a]),pre++,las--;
    sum+=Length(p[a]-*pre)+Length(p[a]-*las);
}
int main()
{
    p[1].x=p[1].y=p[3].y=0.0;
    scanf("%lf%lf%lf%d",&p[3].x,&p[2].x,&p[2].y,&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i+3].x,&p[i+3].y);
    for(int i=1;i<=3;i++) s.insert(p[i]);
    sum+=Length(p[2]-p[1])+Length(p[3]-p[2]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&q[i].op);
        if(q[i].op&1) scanf("%d",&q[i].t),flag[q[i].t+3]=true;
    }
    for(int i=4;i<=n+3;i++)
        if(!flag[i]) Insert(i);
    while(m)
    {
        if(q[m].op&1) Insert(q[m].t+3);
        else ans[++cnt]=sum;
        m--;
    }
    while(cnt) printf("%.2lf\n",ans[cnt]),cnt--;
    return 0;
}