【题解】P2521 [HAOI2011]防线修建(动态凸包)

凸包是易插入不好删除的东西，按照剧情所以我们时光倒流

然后问题就是维护凸包的周长，支持加入

本来很简单，但是计算几何就是一些小地方经验不足容易WA和RE

然后代码注释里有一些经验

//@winlere

#include<iostream>

#include<set>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<cmath>

#define pf(x) ((x)*(x))

#define DEBUG(s,a) cerr<<#s" = "<<(s)<<" \n"[(a)==1]

#define getchar() (__c==__ed?(__ed=__buf+fread(__c=__buf,1,1<<18,stdin),*__c++):*__c++)

using namespace std;  typedef long long ll;   char __buf[1<<18],*__c=__buf,*__ed=__buf;

inline int qr(){

	int ret=0,f=0,c=getchar();

	while(!isdigit(c))f|=c==45,c=getchar();

	while(isdigit(c)) ret=ret*10+c-48,c=getchar();

	return f?-ret:ret;

}

const int maxn=1e5+5;

struct NODE{//向量 坐标用一个结构体代替就行了

	ll x,y;//用ll吧 别小气

	NODE operator - (NODE b)const{return {x-b.x,y-b.y};}

	ll operator % (NODE b)const{return x*b.y-y*b.x;}

	bool operator < (NODE b)const{return x<b.x;}

	double operator ^ (NODE b)const{return sqrt(pf(x-b.x)+pf(y-b.y));}

}data[maxn],capt;

vector< pair<int,int> > ve;

double len,ans[maxn];

bool in[maxn];

set<NODE> s;

void insert(NODE x){

	vector<NODE> ve;

	if((*s.upper_bound(x)-x)%(x-*--s.upper_bound(x))<0) return;//先判断是否能够插入，这样以后好写一些

	for(set<NODE>::iterator t=--s.upper_bound(x),temp;t!=s.begin();t=temp){

		temp=prev(t);

		if((x-*temp)%(*t-*temp)<0) ve.push_back(*t);//避免一边用iterator一边erase

		else break;

	}

	reverse(ve.begin(),ve.end());

	for(set<NODE>::iterator t=s.upper_bound(x),temp;t!=--s.end();t=temp){

		temp=next(t);

		if((*temp-x)%(*temp-*t)>0) ve.push_back(*t);//同上

		else break;

	}

	if(ve.size()==0)//多写几个if比仔细比巧妙统一快得多，对于=0,=1都特判一下，这里只要=0特判

		len+=(*s.upper_bound(x)^x)+(*--s.upper_bound(x)^x)-(*--s.upper_bound(x)^*s.upper_bound(x));

	else {

		auto l=*--s.find(ve.front()),r=*++s.find(ve.back());

		len+=(l^x)+(r^x)-(l^ve.front())-(r^ve.back());

		for(int t=1,ed=ve.size();t<ed;++t) len-=ve[t]^ve[t-1];//多写一个循环没问题

		for(auto t:ve) s.erase(t);

	}

	s.insert(x);

}

int n,m,x,y,q;

int main(){

	n=qr(); capt.x=qr(),capt.y=qr(); m=qr();

	s.insert(capt); s.insert({n,0}); s.insert({0,0}); len=(capt^*s.begin())+(capt^*s.rbegin());

	for(int t=1;t<=m;++t) data[t].x=qr(),data[t].y=qr();

	q=qr();

	for(int t=1;t<=q;++t){

		int op=qr();

		ve.push_back(op==1?(pair<int,int>){op,qr()}:(pair<int,int>){op,t});

		if(op==1) in[ve.back().second]=1;

	}

	for(int t=1;t<=m;++t)

		if(!in[t])

			insert(data[t]);

	reverse(ve.begin(),ve.end());

	for(auto t:ve)

		if(t.first==1) insert(data[t.second]);

		else ans[t.second]=len;

	reverse(ve.begin(),ve.end());

	for(auto t:ve)

		if(t.first==2) printf("%.2lf\n",ans[t.second]);

	return 0;

}

巴特西

【题解】P2521 [HAOI2011]防线修建(动态凸包)

【题解】P2521 [HAOI2011]防线修建(动态凸包)

最新文章

热门文章