正題

題目鏈接:https://www.ybtoj.com.cn/contest/116/problem/3

---

題目大意

給出兩個(gè)大小分別為$n,m$的點(diǎn)集$A,B$。

求出$B$的一個(gè)最小子集使得該子集的凸包包含了所有點(diǎn)集$A$中的點(diǎn)。

無解輸出$?1$

$2\le n\le 10^5,3\le m\le 500$

---

解題思路

選出的子集肯定是一個(gè)凸包，凸包就是相鄰點(diǎn)連邊之間的半平面交。

所以可以理解為我們要找到一些點(diǎn)對(duì)使得它們的半平面包含點(diǎn)集$A$。

如果$x?>y$的半平面（左右都一樣，反過來就是了）包含點(diǎn)集$A$，那么$x$向$y$連邊，那么問題就變?yōu)榱饲髨D的最小環(huán)。這個(gè)可以$Floyd$解決。

如何判斷一個(gè)半平面是否包含點(diǎn)集$A$？

一個(gè)類似旋轉(zhuǎn)卡殼的想法是對(duì)于給出的這個(gè)半平面的斜率，我們?cè)邳c(diǎn)集$A$的凸包上找到兩個(gè)節(jié)點(diǎn)卡住它。（如下圖）

然后判斷這兩個(gè)點(diǎn)是否在半平面內(nèi)就好了。

挺麻煩的，再簡(jiǎn)化一下，我們將$A$的凸包用$x$坐標(biāo)最大/小的兩個(gè)節(jié)點(diǎn)分成兩半，那么凸包就變成了一個(gè)上凸殼和一個(gè)下凸殼。

然后我們要找到的兩個(gè)點(diǎn)，這個(gè)兩個(gè)點(diǎn)肯定是一個(gè)在上一個(gè)在下的，我們根據(jù)半平面的斜率在上下凸殼上面二分一下就好了。

時(shí)間復(fù)雜度$O(n+m^2\log n+m^3)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e5+10,M=510; struct point{ll x,y;point(ll xx=0,ll yy=0){x=xx;y=yy;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.x+b.x,a.y+b.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[top=1]=a[1];for(ll i=2;i<=n;i++){while(top>1&&(s[top]-s[top-1])*(a[i]-s[top-1])*op>=0)top--;s[++top]=a[i];}for(ll i=1;i<=top;i++)a[i]=s[i];return top; } bool check(point a,point b){ll op=1;if(a.x>b.x)swap(a,b),op=-1;ll l=1,r=uc-1;while(l<=r){ll x=(l+r)>>1;if((b-a)*(u[x+1]-u[x])>=0)l=x+1;else r=x-1; }if((b-a)*(u[l]-a)*op<0)return 0;l=1,r=vc-1;while(l<=r){ll x=(l+r)>>1;if((b-a)*(v[x+1]-v[x])<=0)l=x+1;else r=x-1;}if((b-a)*(v[l]-a)*op<0)return 0;return 1; } bool cmp(point a,point b) {return a.x<b.x;} signed main() {freopen("lo.in","r",stdin);freopen("lo.out","w",stdout);scanf("%lld%lld",&n,&m);ll L=1,R=1;for(ll i=1;i<=n;i++)scanf("%lld%lld",&g[i].x,&g[i].y);sort(g+1,g+1+n,cmp);for(ll i=1;i<=n;i++){ll w=(g[n]-g[1])*(g[i]-g[1]);if(w>=0)u[++uc]=g[i];if(w<=0)v[++vc]=g[i];}uc=solve(u,uc,1);vc=solve(v,vc,-1);for(ll i=1;i<=m;i++)scanf("%lld%lld",&p[i].x,&p[i].y);for(ll i=1;i<=m;i++)for(ll j=1;j<=m;j++){if(i==j){h[i][j]=f[i][j]=1e9;continue;}h[j][i]=f[i][j]=check(p[i],p[j])?1:1e9;}for(ll k=1;k<=m;k++)for(ll i=1;i<=m;i++)for(ll j=1;j<=m;j++)f[i][j]=min(f[i][j],f[i][k]+f[k][j]);ans=1e9;for(ll i=1;i<=m;i++)for(ll j=1;j<=m;j++)ans=min(ans,f[i][j]+h[i][j]);if(ans>=1e9)puts("-1");else printf("%lld\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的YbtOJ#832-鸽子饲养【凸包,Floyd】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。