注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2564]集合的面积  

2014-12-18 21:54:04|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2564: 集合的面积

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 167  Solved: 71
[Submit][Status]

Description

  对于一个平面上点的集合P={(xi,yi )},定义集合P的面积F(P)为点集P的凸包的面积。
  对于两个点集AB,定义集合的和为:
  A+B={(xiA+xjB,yiA+yjB ):(xiA,yiA )A,(xjB,yjB )B}
  现在给定一个N个点的集合A和一个M个点的集合B,求2F(A+B)
 

Input

 第一行包含用空格隔开的两个整数,分别为NM
  第二行包含N个不同的数对,表示A集合中的N个点的坐标;
  第三行包含M个不同的数对,表示B集合中的M个点的坐标。

 

Output

 一共输出一行一个整数,2F(A+B)

Sample Input

4 5
0 0 2 1 0 1 2 0
0 0 1 0 0 2 1 2 0 1

Sample Output

18
数据规模和约定
  对于30%的数据满足N ≤ 200,M ≤ 200;
  对于100%的数据满足N ≤ 10^5,M ≤ 10^5,|xi|, |yi| ≤ 10^8。

Solution

首先 这题与凸包有关 不妨从不在A的凸包中的点开始考虑起.

考虑一个不在A的凸包中的点 假如我们确定了一个B中的点的话 那么 A中的所有点都加上这个坐标之后的相对位置不变 A中原先不是凸包的点经过运算后还是不可能出现在凸包内..对B也是这样 这样 我们能确定 构成新的凸包的点肯定是A凸包中的某些点加上B凸包的某些点构成的。

我们可以确定的是 A凸包中最左的点加上B凸包中最左的点在相加之后还是在新凸包内…不妨从这个点开始拓展 观察新的图 我们发现 这个图的形状是一个凸包 然后每个凸包的点上再环绕一个凸包的形状..那么 有了一个基本的贪心策略:每次拓展到一个点之后..那么它只会有2种情况:一种是拓展到原A凸包的下一个点与当前B凸包点的和点中 一种是拓展到原B凸包的下一个与当前A凸包点的和点中..贪心选取其中较“凸”的一个即可..可以很容易发现 新凸包的点数不会超过(N+M) 至此 问题解决

Code

/**************************************************************
    Problem: 2564
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:460 ms
    Memory:24248 kb
****************************************************************/
 
#include<cstdio>
#include<cmath>
#include<algorithm>
const int MAXN=500010;
typedef long long ll;
struct P{ll x,y;};
bool cmp(const P&a,const P&b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}
P operator+(const P&a,const P&b){return (P){a.x+b.x,a.y+b.y};}
P operator-(const P&a,const P&b){return (P){a.x-b.x,a.y-b.y};}
ll dot(const P&a,const P&b){return a.x*b.x+a.y*b.y;}
ll cross(const P&a,const P&b){return a.x*b.y-a.y*b.x;}
void gettb(P*a,int n,P*t,int&t0)
{
    std::sort(a+1,a+1+n,cmp);int i,k;
    for(i=1;i<=n;i++)
    {
        while(t0>1&&cross(a[i]-t[t0-1],t[t0]-t[t0-1])>=0)t0--;
        t[++t0]=a[i];
    }k=t0;
    for(i=n-1;i;i--)
    {
        while(t0>k&&cross(a[i]-t[t0-1],t[t0]-t[t0-1])>=0)t0--;
        t[++t0]=a[i];
    }t0--;
}
 
P a[MAXN],b[MAXN],t[MAXN];
int n,m,t0=0;
int main()
{
    scanf("%d%d",&n,&m);int i,j;
    for(i=1;i<=n;i++)scanf("%lld%lld",&a[i].x,&a[i].y);
    for(i=1;i<=m;i++)scanf("%lld%lld",&b[i].x,&b[i].y);
    gettb(a,n,t,t0);for(i=1;i<=t0;i++)a[i-1]=t[i];n=t0;t0=0;
    gettb(b,m,t,t0);for(i=1;i<=t0;i++)b[i-1]=t[i];m=t0;t0=0;
    P x,y;
    for(i=0,j=0,t[++t0]=a[i]+b[j];i<n||j<m;)
    {
        x=a[i%n]+b[(j+1)%m];
        y=a[(i+1)%n]+b[j%m];
        if(cross(x-t[t0],y-t[t0])>=0)
        {
            t[++t0]=x;j++;
        }
        else
        {
            t[++t0]=y;i++;
        }
    }t0--;ll s=0;
    for(i=2;i<t0;i++)s+=cross(t[i]-t[1],t[i+1]-t[1]);
    printf("%lld\n",s);
}
  评论这张
 
阅读(195)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018