列表

详情

NC237555. Surround the Buildings

描述

Bob is playing a computer game. In this game, the player need to build some forts to protect the villages. The are n villages on the map, the game gives m possible places that you can choose to build forts. A village is protected if and only if there exists three forts and the village is in the triangle of them (edges and vertices are also legal).

Now Bob wants to know the minimum number of forts that he need to build. Because there are too many villages and forts, he asks for your help, can you help him?

输入描述

The first line contains two integers n,m  , indicate the numbers of the villages and the planned sites.

In the following n lines, each line contains two integers x,y , indicates the coordinates of the villages.

In the following m lines, each line contains two integers x,y , indicates the coordinates of the planned sites.

It is guarantee that there doesn`t exist a line across all the villages.

输出描述

If no solution exists, output  on a single line, otherwise output an integer indicating the minimum number of sites to protect all the buildings.

示例1

输入: 

3 6
-1 1
-2 -1
2 0
-3 1
3 1
-1 -4
1 2
-4 -5
3 -4

输出: 

3

示例2

输入: 

3 3
1 1
1 2
2 2
2 1
1 3
0 1

输出: 

-1

说明:

Note that there may be some points with the same coordinate
The red points are villiages and the blue points are the planned sites. One solution of the minimum number of forts that Bob need to build is \textbf{DEF}.

It is easy to figure out that no solution exists.

原站题解

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

C++(g++ 7.5.0) 解法, 执行用时: 2570ms, 内存消耗: 68244K, 提交时间: 2022-09-14 00:22:32 

#include <bits/stdc++.h>

using namespace std;

int fin() {
    int x = 0, f = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (isdigit(c)) {
        x = (x << 1) + (x << 3) + (c - '0');
        c = getchar();
    }
    return x * f;
}

using ll = long long;
using ld = long double;
using mat = vector<vector<int>>;
const int inf = 0x3f3f3f3f;
const ld eps = 1e-9;
const ld PI = acosl(-1);

int sgn(ld x) {
    if (fabsl(x) < eps) return 0;
    if (x > 0) return 1;
    return -1;
}

struct node {
    ld x, y;

    void read() {
        x = fin(), y = fin();
    }

    node rotate(ld alpha) const {
        ld cs = cosl(alpha);
        ld sn = sinl(alpha);
        return {x * cs - y * sn, x * sn + y * cs};
    }

    node operator-(const node &t) const {
        return {x - t.x, y - t.y};
    }

    node operator+(const node &t) const {
        return {x + t.x, y + t.y};
    }

    ld getAlpha() const {
        return atan2l(y, x);
    }

    ld len2() const {
        return x * x + y * y;
    }

    ld len() const {
        return sqrtl(len2());
    }

    ld operator^(const node &t) const {
        return x * t.y - y * t.x;
    }

    bool operator<(const node &t) const {
        if (!sgn(x)) return y < t.y;
        return x < t.x;
    }

    bool operator==(const node &t) const {
        return !sgn(x - t.x) && !sgn(y - t.y);
    }
};

vector<node> tubo(const vector<node> &a, int n) {
    deque<int> q;
    vector<bool> vis(n);
    for (int i = 0; i < n; i++) {
        while (q.size() >= 2) {
            int x = q[q.size() - 2], y = q.back(), z = i;
            node A = a[z] - a[x];
            node B = a[y] - a[x];
            if (sgn(A ^ B) <= 0) {
                q.pop_back();
                vis[y] = 0;
            } else break;
        }
        q.push_back(i);
        vis[i] = 1;
    }
    vis[0] = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (vis[i]) continue;
        while (q.size() >= 2) {
            int x = q[q.size() - 2], y = q.back(), z = i;
            node A = a[z] - a[x];
            node B = a[y] - a[x];
            if (sgn(A ^ B) <= 0) {
                q.pop_back();
            } else break;
        }
        q.push_back(i);
    }
    vector<node> res;
    for (auto to: q) {
        res.push_back(a[to]);
    }
    return res;
}

int main() {
#ifdef _OJ_TEST_
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int n = fin(), m = fin();
    vector<node> a(n), b(m);
    for (auto &x: a) x.read();
    for (auto &y: b) y.read();

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    b.erase(unique(b.begin(), b.end()), b.end());

    a = tubo(a, a.size());
    n = a.size();
    m = b.size();

    vector<vector<int>> e(m);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            if (i == j) continue;
            node A = b[j] - b[i];
            int l = 0, r = n - 2;
            while (l < r) {
                int mid = (l + r + 1) >> 1;
                node B = a[mid + 1] - a[mid];
                if (sgn(A ^ B) <= 0) r = mid - 1;
                else l = mid;
            }
            node B = a[l + 1] - b[i];
            if (sgn(A ^ B) > 0) {
                continue;
            }
            B = a[l] - b[i];
            if (sgn(A ^ B) <= 0) {
                e[i].push_back(j);
            }
        }
    }
    auto bfs = [&](int st) {
        queue<int> q;
        vector<int> dis(m, inf);
        q.push(st);
        dis[st] = 0;
        while (q.size()) {
            auto hd = q.front();
            q.pop();
            for (auto to: e[hd]) {
                if (to == st) {
                    return dis[hd] + 1;
                }
                if (dis[hd] + 1 < dis[to]) {
                    dis[to] = dis[hd] + 1;
                    q.push(to);
                }
            }
        }
        return inf;
    };
    int res = inf;
    for (int st = 0; st < m; st++) {
        res = min(res, bfs(st));
    }
    printf("%d\n", res == inf ? -1 : res);


    return 0;
}

C++ 解法, 执行用时: 1974ms, 内存消耗: 113248K, 提交时间: 2022-05-28 20:47:07 

#include<cstdio>
#include<vector>
#include<algorithm>
#include<bitset>
#include<queue>

using namespace std;

const int INF=1e9;

struct pnt
{
	long long x,y;
	pnt(long long _x=0,long long _y=0):x(_x),y(_y){}
};
bool operator<(pnt A,pnt B){return A.x!=B.x?A.x<B.x:A.y<B.y;}
bool operator==(pnt A,pnt B){return A.x==B.x&&A.y==B.y;}
pnt operator+(pnt A,pnt B){return pnt(A.x+B.x,A.y+B.y);}
pnt operator-(pnt A,pnt B){return pnt(A.x-B.x,A.y-B.y);}
long long operator^(pnt A,pnt B){return A.x*B.y-A.y*B.x;}
typedef pnt vec;

int n,m;
pnt P[2000000],Q[10000];
vector<pnt> U,D;
pnt dD[2000000],dU[2000000];

void get_Convex_Hull()
{
	D.push_back(P[1]);
	for(int i=2;i<=n;i++)
	{
		while(D.size()>=2&&((D[D.size()-1]-D[D.size()-2])^(P[i]-D[D.size()-2]))<=0)D.pop_back();
		D.push_back(P[i]);
	}
	
	U.push_back(P[n]);
	for(int i=n-1;i>=1;i--)
	{
		while(U.size()>=2&&((U[U.size()-1]-U[U.size()-2])^(P[i]-U[U.size()-2]))<=0)U.pop_back();
		U.push_back(P[i]);
	}
}

typedef bitset<5001> BIT;
BIT E[5001],res;int dis[10000];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&P[i].x,&P[i].y);
	}
	sort(P+1,P+n+1);n=unique(P+1,P+n+1)-(P+1);
	get_Convex_Hull();
	
	for(int i=0;i<D.size()-1;i++)dD[i]=D[i+1]-D[i];
	for(int i=0;i<U.size()-1;i++)dU[i]=U[i+1]-U[i];
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld",&Q[i].x,&Q[i].y);
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(i==j)continue;
			int l=0,r=U.size()-1;vec x=Q[j]-Q[i];
			while(l<r)
			{
				int mid=(l+r)>>1;
				if((dU[mid]^x)<=0)l=mid+1;else r=mid;
			}
			if(((U[l]-Q[i])^x)<0)continue;
			
			l=0,r=D.size()-1;
			while(l<r)
			{
				int mid=(l+r)>>1;
				if((dD[mid]^x)<=0)l=mid+1;else r=mid;
			}
			if(((D[l]-Q[i])^x)<0)continue;
			E[i][j]=1;
		}
	}
	//for(int i=1;i<=m;i++){for(int j=1;j<=m;j++)printf("%d",(int)E[i][j]);puts("");}
	///return 0;
	queue<int> q;
	int ans=INF;
	for(int i=1;i<=m;i++)
	{
		//printf("%d:\n",i);
		for(int j=1;j<=m;j++)dis[j]=-1,res[j]=1;
		for(int j=1;j<=m;j++)if(E[i][j])dis[j]=1,q.push(j),res[j]=0;
		while(!q.empty()&&dis[i]==-1)
		{
			int x=q.front();BIT B=E[x]&res;q.pop();
			while(B.any())
			{
				int u=B._Find_first();B[u]=0;res[u]=0;q.push(u);dis[u]=dis[x]+1;
			}
		}
		if(dis[i]!=-1)ans=min(ans,dis[i]);
		while(!q.empty())q.pop();
	}
	printf("%d",ans==INF?-1:ans);
}

上一题

© 2025 nowcoder.com