[JSOI2018]战争

题目描述

九条可怜是一个热爱读书的女孩子。

在她最近正在读的一本小说中，描述了两个敌对部落之间的故事。第一个部落有 nnn 个人，第二个部落有 mmm 个人，每一个人的位置可以抽象成二维平面上坐标为 (xi,yi)(x_i,y_i)(xi,yi) 的点。

在这本书中，人们有很强的领地意识，对于平面上的任何一个点，如果它被三个来自同一部落的人形成的三角形（可能退化成一条线段）包含（包括边界），那么这一个点就属于这一个部落的领地。如果存在一个点同时在两个阵营的领地中，那么这两个部落就会为了争夺这一个点而发生战争。

常年的征战让两个部落不堪重负，因此第二个部落的族长作出了一个英明的决定，他打算选择一个向量 (dx,dy)(dx,dy)(dx,dy) ，让所有的族人都迁徙这个向量的距离，即所有第二阵营的人的坐标都变成 (xi+dx,yi+dy)(x_i+dx,y_i+dy)(xi+dx,yi+dy) 。

现在他计划了 qqq 个迁徙的备选方案，他想要你来帮忙对每一个迁徙方案，计算一下在完成了迁徙之后，两个部落之间还会不会因为争夺领地而发生战争。

输入格式

第一行输入三个整数 n,m,qn,m,qn,m,q，表示两个部落里的人数以及迁徙的备选方案数。

接下来 nnn 行每行两个整数 xi,yix_i,y_ixi,yi 表示第一个部落里的人的坐标。

接下来 mmm 行每行两个整数 xi,yix_i,y_ixi,yi 表示第二个部落里的人的坐标。

接下来 qqq 行每行两个整数 dxi,dyidx_i,dy_idxi,dyi 表示一个迁徙方案。

输入数据保证所有人的坐标两两不同。

输出格式

对于每个迁徙方案，输出一行一个整数，000 表示不会发生冲突，111 表示会发生冲突。

输入输出样例

输入 #1

输出 #1

设a,b为两个部落构成的凸包

b+d=a等价于d=a-b

即取反b，求出凸包，再用Minkowski和合并两凸包

查询用二分查询向量d所在区间，用叉积判断是否在凸包内

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 typedef long long lol;

 struct Node

 {

     lol x,y;

     Node operator + (const Node &b) const

     {

         return (Node){x+b.x,y+b.y};

     }

     Node operator - (const Node &b) const

     {

         return (Node){x-b.x,y-b.y};

     }

 }a[],b[],sa[],sb[],sta[],bs,s1[],s2[],s[];

 int n,m,q,top;

 bool cmp(Node a,Node b)

 {

     if (a.y==b.y) return a.x<b.x;

     return a.y<b.y;

 }

 lol cross(Node a,Node b)

 {

     return (a.x*b.y-a.y*b.x);

 }

 lol dist(Node a)

 {

     return a.x*a.x+a.y*a.y;

 }

 bool cmp1(Node A,Node B)

 {

     lol t=cross((a[]-A),(a[]-B));

     if (t==) return dist(a[]-A)<dist(a[]-B);

     return t>;

 }

 bool cmp2(Node A,Node B)

 {

     lol t=cross((b[]-A),(b[]-B));

     if (t==) return dist(b[]-A)<dist(b[]-B);

     return t>;

 }

 int grahama(int N)

 {int i;

     sort(a+,a+N+,cmp);

     sort(a+,a+N+,cmp1);

     top=;

     sa[++top]=a[];

     if (N==) return ;

     sa[++top]=a[];

     for (i=;i<=N;i++)

     {

         while (top>&&cross(a[i]-sa[top-],sa[top]-sa[top-])>=) top--;

         top++;

         sa[top]=a[i];

     }

     sa[top+]=a[];

     return top;

 }

 int grahamb(int N)

 {int i;

     sort(b+,b+N+,cmp);

     sort(b+,b+N+,cmp2);

     top=;

     sb[++top]=b[];

     if (N==) return ;

     sb[++top]=b[];

     for (i=;i<=N;i++)

     {

         while (top>&&cross(b[i]-sb[top-],sb[top]-sb[top-])>=) top--;

         top++;

         sb[top]=b[i];

     }

     sb[top+]=b[];

     return top;

 }

 bool cmpp(Node A,Node B)

 {

     lol t=cross((s[]-A),(s[]-B));

     if (t==) return dist(s[]-A)<dist(s[]-B);

     return t>;

 }

 int grahams(int N)

 {int i;

     sort(s+,s+N+,cmp);

     sort(s+,s+N+,cmpp);

     top=;

     sta[++top]=s[];

     if (N==) return ;

     sta[++top]=s[];

     for (i=;i<=N;i++)

     {

         while (top>&&cross(s[i]-sta[top-],sta[top]-sta[top-])>=) top--;

         top++;

         sta[top]=s[i];

     }

     sta[top+]=s[];

     return top;

 }

 bool cmp3(Node A,Node B)

 {

     return cross(A,B)>||(cross(A,B)==&&dist(A)<dist(B));

 }

 lol find(Node A)

 {

     if(cross(A,sta[])>||cross(sta[top],A)>) return ;

     lol ps=lower_bound(sta+,sta+top+,A,cmp3)-sta-;

     return cross((A-sta[ps]),(sta[ps%top+]-sta[ps]))<=;

 }

 void Minkowski()

 {

     for(lol i=;i<n;i++) s1[i]=sa[i+]-sa[i];s1[n]=sa[]-sa[n];

     for(lol i=;i<m;i++) s2[i]=sb[i+]-sb[i];s2[m]=sb[]-sb[m];

     top=;

     s[top]=sa[]+sb[];

     lol i=,j=;

     while(i<=n&&j<=m) ++top,s[top]=s[top-]+(cross(s1[i],s2[j])>=?s1[i++]:s2[j++]);

     while(i<=n) ++top,s[top]=s[top-]+s1[i++];

     while(j<=m) ++top,s[top]=s[top-]+s2[j++];

 }

 int main()

 {int i,j;

 lol dx,dy;

     cin>>n>>m>>q;

     for (i=;i<=n;i++)

     scanf("%lld%lld",&a[i].x,&a[i].y);

     for (i=;i<=m;i++)

     scanf("%lld%lld",&b[i].x,&b[i].y),b[i].x=-b[i].x,b[i].y=-b[i].y;

     n=grahama(n);

     m=grahamb(m);

     Minkowski();

     top=grahams(top);

     bs=sta[];

     for (i=;i<=top;i++)

     sta[i]=sta[i]-bs;

     for (i=;i<=q;i++)

     {

         scanf("%lld%lld",&dx,&dy);

         if (find((Node){dx,dy}-bs))

         printf("1\n");

         else printf("0\n");

     }

 }

巴特西

[JSOI2018]战争

题目描述

输入格式

输出格式

输入输出样例

最新文章

热门文章