BZOJ2300: [HAOI2011]防线修建

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2300

(我只是在发以前写过的题。。

因为题目没说强制在线,所以离线乱搞就可以了。先把点删掉然后一个一个插进去,维护一个动态凸包就可以了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
#define esp 1e-7
#define ll long long
#define oo 1152921504606846976
#define rep(i,l,r) for (int i=l;i<=r;i++)
#define down(i,l,r) for (int i=l;i>=r;i--)
using namespace std;
const int maxn=,maxm=;
struct P{int x,y;
}a[maxn],del[maxn];
set<P> q;
double now,ans[maxn];
int top,n,m,mark[maxn],t1,t2,b[maxn];
ll read(){
int x=,f=; char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-; ch=getchar();}
while (isdigit(ch)) x=x*+ch-'',ch=getchar();
return x*f;
}
P operator -(P a,P b){
return (P){a.x-b.x,a.y-b.y};
}
double operator *(P a,P b){
return (a.x*b.y-a.y*b.x);
}
int cmp(double x){
if (fabs(x)<esp) return ;
if (x>) return ;
return -;
}
double dis(P a,P b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool operator <(P a,P b){
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
void insert(P x){
set<P>::iterator r=q.lower_bound(x),l=r,t; l--;
if ((*r-*l)*(x-*l)<) return;
now-=dis(*l,*r);
while (){
t=r++;
if (r==q.end()) break;
if ((*r-x)*(*t-x)>) break;
now-=dis(*r,*t);
q.erase(t);
}
while (l!=q.begin()){
t=l--;
if ((*t-x)*(*l-x)>) break;
now-=dis(*l,*t);
q.erase(t);
}
q.insert(x); l=r=q.find(x); l--;r++;
now+=dis(*r,x)+dis(*l,x);
}
int main(){
int op,x;
n=read();
P bas;
bas.x=read(); bas.y=read();
q.insert((P){,}); q.insert((P){n,}); q.insert(bas);
now+=dis((P){,},bas)+dis((P){n,},bas);
m=read();
rep(i,,m) a[i].x=read(),a[i].y=read();
int Q;
Q=read();
rep(i,,Q){
op=read();
if (op==) {x=read();del[++t1]=a[x]; mark[x]=;}
else b[++t2]=t1;
}
rep(i,,m) if (!mark[i]) insert(a[i]);
int t=t1;
down(i,t2,){
while (t>b[i]) insert(del[t--]);
ans[i]=now;
}
rep(i,,t2) printf("%.2lf\n",ans[i]);
return ;
}
上一篇:rabbitmq 交换机模式 -主题模式 topic


下一篇:【总结】设计模式