牟平建设局网站北留德庄,淮南做网站推广,营销型网站的好处,找事做网站怎么弄正题
题目链接:https://www.ybtoj.com.cn/contest/116/problem/3 题目大意
给出两个大小分别为n,mn,mn,m的点集A,BA,BA,B。
求出BBB的一个最小子集使得该子集的凸包包含了所有点集AAA中的点。
无解输出−1-1−1 2≤n≤105,3≤m≤5002\leq n\leq 10^5,3\leq m\leq 5002≤n≤…正题
题目链接:https://www.ybtoj.com.cn/contest/116/problem/3 题目大意
给出两个大小分别为n,mn,mn,m的点集A,BA,BA,B。
求出BBB的一个最小子集使得该子集的凸包包含了所有点集AAA中的点。
无解输出−1-1−1
2≤n≤105,3≤m≤5002\leq n\leq 10^5,3\leq m\leq 5002≤n≤105,3≤m≤500 解题思路
选出的子集肯定是一个凸包凸包就是相邻点连边之间的半平面交。
所以可以理解为我们要找到一些点对使得它们的半平面包含点集AAA。
如果x−yx-yx−y的半平面左右都一样反过来就是了包含点集AAA那么xxx向yyy连边那么问题就变为了求图的最小环。这个可以FloydFloydFloyd解决。
如何判断一个半平面是否包含点集AAA
一个类似旋转卡壳的想法是对于给出的这个半平面的斜率我们在点集AAA的凸包上找到两个节点卡住它。如下图 然后判断这两个点是否在半平面内就好了。
挺麻烦的再简化一下我们将AAA的凸包用xxx坐标最大/小的两个节点分成两半那么凸包就变成了一个上凸壳和一个下凸壳。
然后我们要找到的两个点这个两个点肯定是一个在上一个在下的我们根据半平面的斜率在上下凸壳上面二分一下就好了。
时间复杂度O(nm2lognm3)O(nm^2\log nm^3)O(nm2lognm3) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510,M510;
struct point{ll x,y;point(ll xx0,ll yy0){xxx;yyy;return;}
}g[N],u[N],v[N],s[N],p[M];
ll n,m,uc,vc,f[M][M],h[M][M],ans;
point operator(point a,point b)
{return point(a.xb.x,a.yb.y);}
point operator-(point a,point b)
{return point(a.x-b.x,a.y-b.y);}
ll operator*(point a,point b)
{return a.x*b.y-a.y*b.x;}
ll solve(point *a,ll n,ll op){ll top;s[top1]a[1];for(ll i2;in;i){while(top1(s[top]-s[top-1])*(a[i]-s[top-1])*op0)top--;s[top]a[i];}for(ll i1;itop;i)a[i]s[i];return top;
}
bool check(point a,point b){ll op1;if(a.xb.x)swap(a,b),op-1;ll l1,ruc-1;while(lr){ll x(lr)1;if((b-a)*(u[x1]-u[x])0)lx1;else rx-1; }if((b-a)*(u[l]-a)*op0)return 0;l1,rvc-1;while(lr){ll x(lr)1;if((b-a)*(v[x1]-v[x])0)lx1;else rx-1;}if((b-a)*(v[l]-a)*op0)return 0;return 1;
}
bool cmp(point a,point b)
{return a.xb.x;}
signed main()
{freopen(lo.in,r,stdin);freopen(lo.out,w,stdout);scanf(%lld%lld,n,m);ll L1,R1;for(ll i1;in;i)scanf(%lld%lld,g[i].x,g[i].y);sort(g1,g1n,cmp);for(ll i1;in;i){ll w(g[n]-g[1])*(g[i]-g[1]);if(w0)u[uc]g[i];if(w0)v[vc]g[i];}ucsolve(u,uc,1);vcsolve(v,vc,-1);for(ll i1;im;i)scanf(%lld%lld,p[i].x,p[i].y);for(ll i1;im;i)for(ll j1;jm;j){if(ij){h[i][j]f[i][j]1e9;continue;}h[j][i]f[i][j]check(p[i],p[j])?1:1e9;}for(ll k1;km;k)for(ll i1;im;i)for(ll j1;jm;j)f[i][j]min(f[i][j],f[i][k]f[k][j]);ans1e9;for(ll i1;im;i)for(ll j1;jm;j)ansmin(ans,f[i][j]h[i][j]);if(ans1e9)puts(-1);else printf(%lld\n,ans);return 0;
}
