傳送門

一眼看出可以倒著做轉為加點維護凸包，然后……然后我就不會了……

看了一眼題解，大概是這樣的，我們先把所有點都讀進來，然后按極角排序，也就是說定義點的大小為他們極角的大小（本題里實際上直接按x坐標和y坐標排序也沒事，代碼里就這樣寫的）

那么我們可以把所有凸包上的點都給扔進一個set里，每次插入一個點的時候找到它的前驅和后繼，然后用叉積計算它到那兩個點的夾角是凹的還是凸的，如果是凸的那么這個點就要加入凸包。然后再往兩邊繼續搜，把所有不應該在凸包里的點給刪掉

因為每個點只會被刪一次，所以插入是均攤\(O(logn)\)的

然后就是調代碼的時候一些比較玄學的事情……一直WA然后調了半天……最后發現幾個變量定義的順序換了一下就可以了？這有什么不對的么我不是很明白誒？

算了……這一個小時就當在劃水好了……

//minamoto #include<bits/stdc++.h> #define IT set<node>::iterator #define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i) #define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i) using namespace std; #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) char buf[1<<21],*p1=buf,*p2=buf; int read(){int res,f=1;char ch;while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');return res*f; } const int N=5e5+5; struct node{int x,y;node(int X=0,int Y=0):x(X),y(Y){} }p[N];set<node>A; int n,x,y,m,q,tot;bool vis[N];double now; struct qqq{int op,i;}op[N];double ans[N]; inline node operator -(node a,node b){return node(a.x-b.x,a.y-b.y);} inline double operator *(node a,node b){return a.x*b.y-b.x*a.y;} inline bool operator <(node a,node b){return a.x==b.x?a.y>b.y:a.x<b.x;} inline double dis(node a,node b){return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));} void ins(node x){IT r=A.lower_bound(x),l=r,t;--l;if((*l-x)*(*r-x)<0)return;now-=dis(*l,*r);while(r!=A.end()){t=r,++r;if((*r-x)*(*t-x)>0)break;now-=dis(*t,*r),A.erase(t);}while(l!=A.begin()){t=l,--l;if((*t-x)*(*l-x)>0)break;now-=dis(*t,*l),A.erase(t);}A.insert(x),l=r=t=A.find(x),--l,++r;now+=dis(*l,x)+dis(*r,x); } int main(){ // freopen("testdata.in","r",stdin);n=read(),x=read(),y=read(),m=read();fp(i,1,m)p[i].x=read(),p[i].y=read();q=read();fp(i,1,q){op[i].op=read();if(op[i].op==1)op[i].i=read(),vis[op[i].i]=true;}now+=dis(node(0,0),node(x,y)),now+=dis(node(x,y),node(n,0));A.insert(node(0,0)),A.insert(node(n,0)),A.insert(node(x,y));fp(i,1,m)if(!vis[i])ins(p[i]);fd(i,q,1)if(op[i].op==1)ins(p[op[i].i]);else ans[++tot]=now;fd(i,tot,1)printf("%.2lf\n",ans[i]);return 0; }

轉載于:https://www.cnblogs.com/bztMinamoto/p/10009281.html

總結

以上是生活随笔為你收集整理的P2521 [HAOI2011]防线修建的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。