洛谷2521 [HAOI2011]防线修建

Luogu

分析

将删除变成添加,然后用set来维护上凸壳即可。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const int M=200000+10;

struct Point { int x,y; } p[N];
typedef Point Vector;
bool operator <(Point a,Point b) { return a.x==b.x?a.y<b.y:a.x<b.x; }
Vector operator -(Point a,Point b) { return (Point){a.x-b.x,a.y-b.y}; }
inline int cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; }

inline double dis(Point a,Point b) {
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline double dis(int a,int b,int c,int d) {
    return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}

struct query { int op,x; } q[M];

set<Point> S;
double Ans[M],ans;
int mark[M],n;

inline void modify(int id) {
    Point x=p[id];
    set<Point>::iterator it=S.upper_bound(x);
    Point nxt=*it; --it; Point pre=*it;
    if (x.x==nxt.x) return;
    if (cross(x-pre,nxt-x)>=0) return;
    ans-=dis(pre,nxt);
    while (pre.x!=0||pre.y!=0) {
        --it; Point t=*it;
        if (cross(pre-t,x-pre)>=0)
            ans-=dis(pre,t),S.erase(S.find(pre)),pre=t;
        else break;
    }
    it=S.find(nxt);
    while (nxt.x!=n||nxt.y!=0) {
        ++it; Point t=*it; 
        if (cross(nxt-x,t-nxt)>=0)
            ans-=dis(nxt,t),S.erase(S.find(nxt)),nxt=t;
        else break;
    }
    ans+=dis(pre,x)+dis(nxt,x);
    S.insert(x);
}

int main() {
    n=read(); int x=read(),y=read(),m=read();
    for (re int i=1;i<=m;++i) p[i].x=read(),p[i].y=read();
    int Q=read();
    for (re int i=1;i<=Q;++i) {
        q[i].op=read();
        if (q[i].op==1) q[i].x=read(),mark[q[i].x]=1;
    }

    S.insert((Point){0,0}),S.insert((Point){n,0}),S.insert((Point){x,y});
    ans=dis(0,0,x,y)+dis(n,0,x,y);
    for (re int i=1;i<=m;++i)
        if (!mark[i]) modify(i);
    
    for (re int i=Q;i>=1;--i) {
        if (q[i].op==1) modify(q[i].x);
        else Ans[i]=ans;
    }

    for (re int i=1;i<=Q;++i)
        if (q[i].op==2) printf("%.2f\n",Ans[i]);
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 24 PM

4 条评论

  1. smy

    所以怎么维护啊qwq

    1. M_sea
      @smy

      代码不是很清楚吗(

      1. smy
        @M_sea

        那还不如直接放代码

  2. smy

    %%%这都会

发表评论