[HAOI2011]防线修建

C++(g++ 7.5.0) 解法, 执行用时: 73ms, 内存消耗: 3240K, 提交时间: 2022-11-29 18:38:09

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using db = long double;

const ll eps = 0;

struct point{
	ll x, y;
    bool operator == (const point &a) const{
    	return abs(x-a.x)<=eps and abs(y-a.y)<=eps;
    }
    bool operator < (const point &a) const{
    	if(abs(x-a.x)<=eps) return y < a.y-eps;
    	return x < a.x-eps;
    }
    friend point operator * (const ll k, const point &a){
    	return {k*a.x, k*a.y};
    }
    point operator + (const point &a) const{
    	return {x+a.x, y+a.y};
    }
    point operator - (const point &a) const{
    	return {x-a.x, y-a.y};
    }
    ll operator * (const point &a) const{
    	return x*a.x + y*a.y;
    }
    ll operator ^ (const point &a) const{
    	return x*a.y - y*a.x;
    }
    int to_left(const point &a) const{
    	const auto t = (*this)^a;
    	return (t>eps)-(t<-eps);
    }
    friend db dist(const point &a, const point &b){
    	return sqrtl((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }
};

struct argcmp{
	bool operator()(const point &u, const point &v) const{
		const auto quad = [](const point &a){
			if(a.y<-eps) return 1;
			if(a.y>eps) return 4;
			if(a.x<-eps) return 5;
			if(a.x>eps) return 3;
			return 2;
		};
		const int qa = quad(u), qb = quad(v);
		if(qa != qb) return qa < qb;
		auto t = u^v;
		if(abs(t)<=eps) return u*u<v*v-eps;
		return t>eps;
	}
};

db sum = 0;
struct dynamic_convex{
	set<point, argcmp> s;
	point o;

	auto pre(decltype(s.begin()) it) const {if(it==s.begin()) it = s.end(); it--; return it;}
	auto nxt(decltype(s.begin()) it) const {it++; if(it==s.end()) it = s.begin(); return it;}

	void add_point(point a) {
		if(s.size()<=1) s.insert(a);
		else if(s.size()==2){
			auto u = *s.begin(), v = *s.rbegin();
			o = (3*u + 3*v + 3*a); o.x/=3, o.y/=3;
			s = {3*u-o, 3*v-o, 3*a-o};
			sum = dist(3*u, 3*v) + dist(3*v, 3*a) + dist(3*a, 3*u); 
		}
		else{
			if(is_in(a)) return;
			a = 3*a - o;
			auto it = s.insert(a).first;
			sum -= dist(*pre(it), *nxt(it));
			auto now = nxt(it);
			while(s.size()>3 and (*now-a).to_left(*nxt(now)-*now)<=0) {
				sum -= dist(*now, *nxt(now));
				s.erase(now), now = nxt(it);
			}
			now = pre(it);
			while(s.size()>3 and (*now-*pre(now)).to_left(a-*now)<=0) {
				sum -= dist(*now, *pre(now));
				s.erase(now), now = pre(it);
			}
			sum += dist(*it, *nxt(it));
			sum += dist(*it, *pre(it));
		}
	}
	bool is_in(point a) const{
		a = 3*a - o;
		auto it = s.lower_bound(a);
		if(it==s.end()) it = s.begin();
		return (*it - *pre(it)).to_left(a-*it)>=0;
	}
}dc;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

    ll n,x,y; cin >> n >> x >> y;
    dc.add_point({0,0}), dc.add_point({n, 0}), dc.add_point({x, y});

    int m; cin >> m;
    vector<point>vec(m);
    for(auto &[x,y]: vec) cin >> x >> y;

    int q; cin >> q;
    vector<pair<int,int>>query(q);
    vector<bool>vis(m, false);
    for(int i = 0 ; i < q ; i ++){
    	int op; cin >> op;
    	if(op==1){
    		int id; cin >> id;
    		query[i] = {1, id}, vis[id-1] = true;
    	}
    	else query[i] = {2, 0};
    }
    for(int i = 0 ; i < m ; i ++) if(!vis[i]) dc.add_point(vec[i]);

    vector<db>ans;
    reverse(query.begin(), query.end());
    for(auto &[op, id]: query){
    	if(op==2) ans.push_back(sum);
    	else dc.add_point(vec[id-1]);
    }
    reverse(ans.begin(), ans.end());
    for(auto &val: ans) cout << fixed << setprecision(2) << val/3-n << '\n';

	return 0;
}

C++ 解法, 执行用时: 66ms, 内存消耗: 2168K, 提交时间: 2022-02-13 11:43:57

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
struct point
{
    int x,y;
}del[100005],a[200005];
 
double now,res[200005];
int T;
int t1,t2;
int n,m,Q;
int b[200005];
bool mark[100005];
set<point> q;
 
double dis(point a,point b)
{
    return sqrt((double)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}
 
bool operator<(point a,point b)
{
    if(a.x==b.x)return a.y<b.y;
    return a.x<b.x;
}
 
int operator*(point a,point b)
{
    return a.x*b.y-a.y*b.x;
}
 
point operator-(point a,point b)
{
    point t;
    t.x=a.x-b.x;t.y=a.y-b.y;
    return t;
}
 
void insert(int a,int b)
{
    point x=(point){a,b};
    set<point>::iterator r=q.lower_bound(x),l=r,t;
    l--;
    if((*r-*l)*(x-*l)<0)return;
    now-=dis(*l,*r);
    q.insert(x);
    while(1){
        t=r;r++;
        if(r==q.end())break;
        if((*r-x)*(*t-x)>0)break;
        now-=dis(*t,*r);
        q.erase(t);
    }
    while(l!=q.begin()){
        t=l;l--;
        if((*t-x)*(*l-x)>0)break;
        now-=dis(*t,*l);
        q.erase(t);
    }
    q.insert(x);
    l=r=t=q.find(x);
    l--;r++;
    now+=dis(*l,x)+dis(*r,x);
}
int main()
{
    scanf("%d",&n);
    q.insert((point){0,0});q.insert((point){n,0});
    point bas;
    scanf("%d%d",&bas.x,&bas.y);
    q.insert(bas);
    now+=dis((point){0,0},bas);
    now+=dis((point){n,0},bas);
    scanf("%d",&m);
    for(int i=1;i<=m;i++) scanf("%d%d",&a[i].x,&a[i].y);
    int typ,x;
    scanf("%d",&Q);
    for(int i=1;i<=Q;i++){
        scanf("%d",&typ);
        if(typ==1){
            scanf("%d",&x);
            del[++t1]=a[x];
            mark[x]=1;
        }
        else b[++t2]=t1;
    }
    for(int i=1;i<=m;i++)
        if(!mark[i])insert(a[i].x,a[i].y);
    int T=t1;
    for(int i=t2;i;i--){
        while(T>b[i]){
            insert(del[T].x,del[T].y);
            T--;
        }
        res[i]=now;
    }
    for(int i=1;i<=t2;i++)printf("%.2f\n",res[i]);
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 50ms, 内存消耗: 2168K, 提交时间: 2020-08-27 16:09:06

#include<bits/stdc++.h>
#define ll long long
using namespace std;

struct point
{
    int x,y;
}del[100005],a[200005];

double now,res[200005];
int T;
int t1,t2;
int n,m,Q;
int b[200005];
bool mark[100005];
set<point> q;

double dis(point a,point b)
{
	return sqrt((double)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}

bool operator<(point a,point b)
{
	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}

int operator*(point a,point b)
{
	return a.x*b.y-a.y*b.x;
}

point operator-(point a,point b)
{
	point t;
	t.x=a.x-b.x;t.y=a.y-b.y;
	return t;
}

void insert(int a,int b)
{
	point x=(point){a,b};
	set<point>::iterator r=q.lower_bound(x),l=r,t;
	l--;
	if((*r-*l)*(x-*l)<0)return;
	now-=dis(*l,*r);
	q.insert(x);
	while(1){
		t=r;r++;
		if(r==q.end())break;
		if((*r-x)*(*t-x)>0)break;
		now-=dis(*t,*r);
		q.erase(t);
	}
	while(l!=q.begin()){
		t=l;l--;
		if((*t-x)*(*l-x)>0)break;
		now-=dis(*t,*l);
		q.erase(t);
	}
	q.insert(x);
	l=r=t=q.find(x);
	l--;r++;
	now+=dis(*l,x)+dis(*r,x);
}
int main()
{
	scanf("%d",&n);
	q.insert((point){0,0});q.insert((point){n,0});
	point bas;
	scanf("%d%d",&bas.x,&bas.y);
	q.insert(bas);
	now+=dis((point){0,0},bas);
	now+=dis((point){n,0},bas);
	scanf("%d",&m);
	for(int i=1;i<=m;i++) scanf("%d%d",&a[i].x,&a[i].y);
	int typ,x;
	scanf("%d",&Q);
	for(int i=1;i<=Q;i++){
		scanf("%d",&typ);
		if(typ==1){
            scanf("%d",&x);
            del[++t1]=a[x];
            mark[x]=1;
        }
		else b[++t2]=t1;
	}
	for(int i=1;i<=m;i++)
		if(!mark[i])insert(a[i].x,a[i].y);
	int T=t1;
	for(int i=t2;i;i--){
		while(T>b[i]){
			insert(del[T].x,del[T].y);
			T--;
		}
		res[i]=now;
	}
	for(int i=1;i<=t2;i++)printf("%.2f\n",res[i]);
	return 0;
}

详情