锐客网

  1. 首页 > it技术 > >

凸包|bzoj5317: [Jsoi2018]部落战争【凸包/Minkowski sum】

bzoj凸包

传送门
解题思路： 【凸包|bzoj5317: [Jsoi2018]部落战争【凸包/Minkowski sum】】先求凸包。
合法向量相当于凸包A中存在一点经过该向量可到凸包B中。
即A+v? =BA + v → = B，那么 v? =A?Bv → = A ? B
画图发现，这些向量的轮廓就是凸包A绕取反后凸包B坐标平移一圈。
好像这个东西也叫Minkowski sum，即求 {v? =a? +b? ,a? ∈A,b? ∈B}{ v → = a → + b → , a → ∈ A , b → ∈ B }

#include #define ll long long using namespace std; int getint() { int i=0,f=1; char c; for(c=getchar(); (c!='-')&&(c<'0'||c>'9'); c=getchar()); if(c=='-')c=getchar(),f=-1; for(; c>='0'&&c<='9'; c=getchar())i=(i<<3)+(i<<1)+c-'0'; return i*f; }const int N=100005; struct point { ll x,y; point(ll _x=0,ll _y=0):x(_x),y(_y){} inline friend point operator + (const point &a,const point &b){return point(a.x+b.x,a.y+b.y); } inline friend point operator - (const point &a,const point &b){return point(a.x-b.x,a.y-b.y); } inline friend ll operator * (const point &a,const point &b){return a.x*b.y-a.y*b.x; } inline ll dis(){return x*x+y*y; } }p[N],p1[N],p2[N],t[N],v1[N],v2[N]; inline bool cmp(const point &a,const point &b) { ll ret=(a-t[1])*(b-t[1]); if(ret)return ret>0; else return (a-t[1]).dis()<(b-t[1]).dis(); } int n,m,tot,Q; int Graham(point *p,int cnt) { for(int i=1; i<=cnt; i++)t[i]=p[i]; for(int i=2; i<=cnt; i++)if(t[i].x=2&&(t[top]-t[top-1])*(t[i]-t[top-1])<=0)top--; t[++top]=t[i]; } for(int i=1; i<=top; i++)p[i]=t[i]; return top; } void go() { for(int i=1; i<=n; i++)v1[i]=p1[i%n+1]-p1[i]; for(int i=1; i<=m; i++)v2[i]=p2[i%m+1]-p2[i]; int l1=1,l2=1; p[tot=1]=p1[1]+p2[1]; while(l1<=n&&l2<=m)p[++tot]=p[tot-1]+(v1[l1]*v2[l2]>=0?v1[l1++]:v2[l2++]); while(l1<=n)p[++tot]=p[tot-1]+v1[l1++]; while(l2<=m)p[++tot]=p[tot-1]+v2[l2++]; tot=Graham(p,tot); } int in(point x) { if((x-p[1])*(p[2]-p[1])>0||(x-p[1])*(p[tot]-p[1])<0)return 0; int l=2,r=tot,pos=l; while(l<=r) { int mid=l+r>>1; if((p[mid]-p[1])*(x-p[1])>=0)pos=mid,l=mid+1; else r=mid-1; } return (p[pos%tot+1]-p[pos])*(x-p[pos])>=0; } int main() { //freopen("war.in","r",stdin); //freopen("war.out","w",stdout); n=getint(),m=getint(),Q=getint(); for(int i=1; i<=n; i++)p1[i].x=getint(),p1[i].y=getint(); for(int i=1; i<=m; i++)p2[i].x=-getint(),p2[i].y=-getint(); n=Graham(p1,n),m=Graham(p2,m); go(); while(Q--) { point q; q.x=getint(),q.y=getint(); printf("%d\n",in(q)); } return 0; } ?

    推荐阅读


    上一篇：Tensorflow 逻辑回归处理mnist数据集

    下一篇：MNIST用matplotlib实现可视化