列表

详情

NC233187. Dynamic Convex Hull

描述

There are N points.

You will be given M queries. Each query will give you several points. You must answer the area of the convex hull of these points merged with the initial N points.

输入描述

This problem contains multiple test cases.

The first line contains an integer T  — the number of test cases.

For each test case:

The first line contains an integer N  — the number of the initial points.

Then N lines follow. The i-th of them contains two integers  — the coordinate of the i-th initial point.

The next line contains an integer M  — the number of queries.

Then M queries follow. For each query: the first line contains an integer  — the number of points in this query; then k lines follow, the i-th of which contains two integers  — the coordinate of the i-th point in this query.

It is guaranteed that in all test cases, the sum of N is no more than , and the sum of k is no more than .

输出描述

For each query in each test case, output  in one line. S indicates the area in this query.

It can be proved that  is always an integer.

示例1

输入: 

1
8
-1 2
-2 1
-2 -1
-1 -2
1 -2
2 -1
2 1
1 2
1
3
0 3
0 4
1 5

输出: 

39

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 1212ms, 内存消耗: 16836K, 提交时间: 2022-05-11 13:28:58 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 0;
double sgn(double x)
{
	return x<-eps ? -1 : x>eps ? 1 : 0;
}
struct point
{
	ll x, y;
	int id = -1;
	bool operator==(const point& a)const { return abs(x - a.x) <= eps && abs(y - a.y) <= eps; }
	bool operator<(const point& a)const { return abs(x - a.x) <= 0 ? y < a.y - eps : x < a.x - eps; }
	ll operator^(const point& a)const { return x * a.y - y * a.x; }
	point operator*(const ll& k) const { return { k * x, k * y }; }
	ll operator*(const point& a)const { return x * a.x + y * a.y; }
	double dis(const point& a)const { return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y)); }
	double len()const { return sqrt(x * x + y * y); }
	point operator-(const point& a)const { return { x - a.x, y - a.y }; }
	point operator-()const { return { -x, -y }; }
	point operator+(const point& a)const { return { x + a.x, y + a.y }; }
};

struct line
{
	point p, v;
	line() :p(), v() {};
	line(point a, point b) :p(a), v(b) {};
	double dis(const point& a)const { return  abs(v ^ (a - p)) / v.len(); }
	point inter(const line& a)const { return p + v * ((a.v ^ (p - a.p)) / (v ^ a.v)); }//两直线相交
};

bool ons(point a1, point a2, point p)//判点p在线段a1,a2上
{
	if (sgn((p - a1) ^ (p - a2)) != 0)return false;
	if (p == a1 || p == a2)return true;
	return sgn((a1 - p) * (a2 - p)) <= 0;
}

struct polygon
{
	vector<point> p;

	size_t nxt(const size_t i) const { return i == p.size() - 1 ? 0 : i + 1; }
	size_t pre(const size_t i) const { return i == 0 ? p.size() - 1 : i - 1; }


	double circ() const
	{
		double sum = 0;
		for (size_t i = 0; i < p.size(); i++) sum += p[i].dis(p[nxt(i)]);
		return sum;
	}

	double area2() const
	{
		double sum = 0;
		for (size_t i = 0; i < p.size(); i++) sum += p[i] ^ p[nxt(i)];
		return abs(sum);
	}
};

struct Convex : polygon
{
	vector<ll>sum;

	void get_sum()
	{
		const auto& p = this->p;
		vector<ll> a(p.size());
		for (size_t i = 0; i < p.size(); i++) a[i] = p[this->pre(i)] ^ p[i];
		sum.resize(p.size());
		partial_sum(a.begin(), a.end(), sum.begin());
	}

	ll query_sum(const size_t l, const size_t r) const
	{
		const auto& p = this->p;
		if (l <= r) return sum[r] - sum[l] + (p[r] ^ p[l]);
		return sum[p.size() - 1] - sum[l] + sum[r] + (p[r] ^ p[l]);
	}
	ll query_sum() const { return sum.back(); }

	int is_in(const point& a)const//判断点是否在凸包内log复杂度 1表示在内部 -1表示在边界 0 表示在外部
	{
		if (p.size() == 1 && a == p[0])return -1;
		if (p.size() == 2 && ons(p[0], p[1], a))return -1;
		if (a == p[0])return -1;
		int l = 1, r = p.size() - 2;
		while (l <= r)
		{
			int mid = (l + r) >> 1;
			const auto t1 = (p[mid] - p[0]) ^ (a - p[0]), t2 = (p[mid + 1] - p[0]) ^ (a - p[0]);
			if (t1 >= 0 && t2 <= 0)
			{
				if (mid == 1 && ons(p[0], p[mid], a))return -1;
				if (mid + 1 == p.size() - 1 && ons(p[0], p[mid + 1], a))return -1;
				if (ons(p[mid], p[mid + 1], a))return -1;
				return ((p[mid + 1] - p[mid]) ^ (a - p[mid])) > 0;
			}
			if (t1 < 0)r = mid - 1;
			else l = mid + 1;
		}
		return 0;
	}

	template<typename F>size_t extreme(const F& dir)const
	{
		const auto& p = this->p;
		const auto check = [&](const size_t i) {return (dir(p[i]) ^ (p[this->nxt(i)] - p[i])) >= 0; };
		const auto dir0 = dir(p[0]); const auto check0 = check(0);
		if (!check0 && check(p.size() - 1))return 0;
		const auto cmp = [&](const point& v)
		{
			const size_t vi = &v - p.data();
			const auto checkv = check(vi);
			const auto t = (dir0 ^ (v - p[0]));
			return checkv ^ (checkv == check0 && ((!check0 && t <= 0) || (check0 && t < 0)));
		};
		return partition_point(p.begin(), p.end(), cmp) - p.begin();
	}

	pair<int, int>tangent(const point& a)const //求a与凸包的两个切点 ,返回（相对于点左边的切点，相对于点右边的切点）
	{
		const size_t i = extreme([&](const point& u) {return u - a; });
		const size_t j = extreme([&](const point& u) {return a - u; });
		return { i,j };
	}

	pair<size_t, size_t> tangent(const line& a) const //求直线平移后与凸包的两个切点,返回（相对于点左边的切点，相对于点右边的切点）
	{
		const size_t i = extreme([&](...) {return a.v; });
		const size_t j = extreme([&](...) {return -a.v; });
		return { i,j };
	}
};

vector<point> convexhull(vector<point>p)
{
	vector<point>st;
	sort(p.begin(), p.end());
	const auto check = [](const vector<point>& st, const point& u)
	{
		const auto back1 = st.back(), back2 = *prev(st.end(), 2);
		return ((back1 - back2) ^ (u - back2)) <= 0;
	};
	for (const point& u : p)
	{
		while (st.size() >= 2 && check(st, u))st.pop_back();
		st.push_back(u);
	}
	int k = st.size();
	p.pop_back(), reverse(p.begin(), p.end());
	for (const point& u : p)
	{
		while (st.size() > k && check(st, u))st.pop_back();
		st.push_back(u);
	}
	st.pop_back();
	return st;
}

long long solve(const Convex& poly, const vector<point>& vec)
{
	if (poly.p.size() <= 10)
	{
		vector<point> tmp = vec;
		tmp.insert(tmp.end(), poly.p.begin(), poly.p.end());
		Convex t;t.p = convexhull(tmp); t.get_sum();
		return t.query_sum();
	}
	vector<point> tmp;
	for (point u : vec)
	{
		if (poly.is_in(u)) continue;
		const auto [x, y] = poly.tangent(u);
		point px = poly.p[x], py = poly.p[y];
		px.id = x; py.id = y;
		tmp.push_back(u);
		tmp.push_back(px);
		tmp.push_back(py);
	}
	if (tmp.empty()) return poly.query_sum();
	Convex t;t.p = convexhull(tmp); t.get_sum();
	long long ans = t.query_sum();
	for (size_t i = 0; i < t.p.size(); i++)
	{
		const auto j = t.nxt(i);
		if (t.p[i].id != -1 && t.p[j].id != -1)
		{
			ans += poly.query_sum(t.p[i].id, t.p[j].id);
		}
	}
	return ans;
}
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int n;
		scanf("%d", &n);
		vector<point>tmp(n);
		for (int i = 0; i < n; i++)
		{
			int x, y;
			scanf("%d%d", &x, &y);
			tmp.push_back({ x,y });
		}
		Convex pp;
		pp.p = convexhull(tmp);
		pp.get_sum();
		int m;
		cin >> m;
		for (int i = 1; i <= m; i++)
		{
			int k;
			scanf("%d", &k);
			vector<point>tmp(k);
			for (int j = 0; j < k; j++)
			{
				int x, y;
				scanf("%d%d", &x, &y);
				tmp.push_back({ x,y });
			}
			printf("%lld\n", solve(pp, tmp));
		}
	}
	getchar(); getchar();
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 1165ms, 内存消耗: 6236K, 提交时间: 2022-11-25 16:57:42 

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

using ll = long long;

constexpr ll eps = 0;

struct point{
	ll x, y;
	bool operator < (const point &a) const{
		if(abs(x-a.x)<=eps) return y < a.y-eps;
		return x < a.x-eps;
	}
	bool operator == (const point &a) const{
		return abs(x-a.x)<=eps and abs(y-a.y)<=eps;
	}
	point operator - () const{
		return {-x, -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);
	}
};

struct line{
	point p, v;
};

struct segment{
	point a,b;
	int is_on(const point &p) const{
		if(p==a or p==b) return -1;
		return (p-a).to_left(p-b)==0 and (p-a)*(p-b)<-eps;
	}
};

struct convex{
	vector<point>p;
	size_t nxt(const size_t i) const{
		return i==p.size()-1?0:i+1;
	}
	size_t pre(const size_t i) const{
		return i==0?p.size()-1:i-1;
	}
	ll area2(){
		ll sum = 0;
		for(size_t i = 0 ; i < p.size() ; i ++) sum += (p[i]^p[nxt(i)]);
		return sum;
	}
	template<typename F> size_t extreme(const F &dir) const{
		const auto &p = this->p;
		const auto check = [&](const size_t i){
			return dir(p[i]).to_left(p[nxt(i)]-p[i])>=0;
		};
		const auto dir0 = dir(p[0]);
		const auto check0 = check(0);
		if(!check0 and check(p.size()-1)) return 0;
		const auto cmp = [&](const point &v){
			const size_t &vi = &v-p.data();
			if(vi==0) return 1;
			const auto checkv = check(vi);
			const auto t = dir0.to_left(v-p[0]);
			if(vi==1 and checkv==check0 and t==0) return 1;
			return checkv ^ (checkv==check0 and t<=0);
		};
		return partition_point(begin(p), end(p), cmp) - begin(p);
    }
    int is_in(const point &a) const{
    	const auto &p = this->p;
    	if(p.size()==1) return a==p[0]?-1:0;
    	if(p.size()==2) return segment{p[0], p[1]}.is_on(a)?-1:0;
    	if(a==p[0]) return -1;
    	if((p[1]-p[0]).to_left(a-p[0])==-1 or (p.back()-p[0]).to_left(a-p[0])==1) return 0;
		const auto cmp = [&](const point &u, const point &v){
			return (u-p[0]).to_left(v-p[0])==1;
		};
	    const size_t i = lower_bound(begin(p)+1, end(p), a, cmp)-begin(p);
	    if(i==1) return segment{p[0], p[i]}.is_on(a)?-1:0;
	    if(i==p.size()-1 and segment{p[0], p[i]}.is_on(a)) return -1;
        return (p[i]-p[i-1]).to_left(a-p[i-1]) > 0;
    }
    pair<size_t, size_t> tangent(const point &a) const{
    	const size_t i = extreme([&](const point &u){return u-a;});
    	const size_t j = extreme([&](const point &u){return a-u;});
    	return {i, j};
    }

    vector<ll>sum;
    void init_sum(){
    	size_t n = p.size();
    	sum.assign(n+1, 0);
    	for(size_t i = 1 ; i <= n ; i ++){
    		sum[i] = (p[i-1]^p[nxt(i-1)]);
    	}
    	for(size_t i = 1 ; i <= n ; i ++){
    		sum[i] += sum[i-1];
    	}
    }
    ll get_area(int l, int r){
    	if(l<r) return sum[r] - sum[l] + (p[r]^p[l]);
    	else return sum[p.size()]-sum[l] + sum[r] + (p[r]^p[l]);
    }
};

convex ConvexHull(vector<point>p){
	vector<point> st;
	if(p.empty()) return convex{st};
	sort(begin(p), end(p));
	const auto check = [](const vector<point>&st, const point &u){
		const auto back1 = st.back(), back2 = *prev(st.end(), 2);
		return (back1-back2).to_left(u-back1) <= 0;		
	};
	for(const auto &u: p){
		while(st.size()>1 and check(st, u)) st.pop_back();
		st.push_back(u);
	}
	size_t k = st.size();
	p.pop_back(); reverse(begin(p), end(p));
	for(const auto &u: p){
		while(st.size()>k and check(st, u)) st.pop_back();
		st.push_back(u);
	}
	st.pop_back();
	return convex{st};
}

void solve(){
    int n; cin >> n;
    vector<point>vec(n);
    for(auto &[x,y]: vec) cin >> x >> y;

    auto c = ConvexHull(vec);
    ll old_area = c.area2();
    n = c.p.size();
    c.init_sum();

    int m; cin >> m;
    while(m--){
    	int k; cin >> k;
    	vector<point>tmp(k);
    	for(auto &[x,y]: tmp) cin >> x >> y;

    	vector<pair<size_t, size_t>>seg;
        vector<point>all;
        for(const auto &u: tmp){
        	if(c.is_in(u)!=0) continue;

        	auto [l,r] = c.tangent(u);
        	seg.push_back({l, r});
        	all.push_back(u);
        	all.push_back(c.p[l]);
            all.push_back(c.p[r]);
        }
        ll del_area = ConvexHull(all).area2();
         
        auto merge = [](vector<pair<size_t, size_t>>&seg, int n)->void{
        	vector<pair<size_t, size_t>>tmp;
        	for(auto [l, r]: seg){
        		if(l<r) tmp.push_back({l, r});
        		else tmp.push_back({0, r}), tmp.push_back({l, n});
        	}
        	sort(tmp.begin(), tmp.end());
        	seg.clear();
        	for(auto [l,r]: tmp){
        		if(seg.empty()) seg.push_back({l, r});
        		else{
        			auto &[l0, r0] = seg.back();
        			if(l<=r0) r0 = max(r0, r);
        			else seg.push_back({l, r});
        		}
        	}
        	if(seg[0]==pair<size_t, size_t>{0,n}) {
        		seg[0] = {0,0};
        	}
        	else if(seg.size()>=2){
        		auto [l1,r1] = seg[0];
        		auto [l2,r2] = seg.back();
        		if(r2==n) seg[0] = {l2, r1}, seg.pop_back();
        	}
        };
        merge(seg, n);

        ll ans = old_area + del_area;
        // cout << old_area << ' ' << del_area << endl;
    	vector<point>inner; 
    	for(auto [l,r]: seg){
    		// cout << l << ' ' << r << endl;
    		ans -= c.get_area(l, r);
    		inner.push_back(c.p[l]);
    		inner.push_back(c.p[r]);
    	}
    	ans -= ConvexHull(inner).area2();
        cout << ans << '\n';
    }
}

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

    int t; cin >> t;
    while(t--){
    	solve();
    }

	return 0;
}

上一题

© 2024 nowcoder.com