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

ydc的博客

 
 
 

日志

 
 

bzoj 3311 Line of Sight  

2013-11-24 20:21:18|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这题竟然没想出来……
果然连usaco水平都没有

今天考了usaco这次的金组,题目对应bzoj的3310~3312(
一、三题自然是切了的……第二题第一眼看上去啥都没想就以为是那种根据单调性扫扫的题
于是开始写,极角排序然后二分,然后画了个图,尼玛根本没有单调性!!!
然后就不会做了(你个逗逼)

一个显然的事实是,如果两个人能相互看见,那么过他们引切线夹住的弧长一定有公共部分。于是就是判断区间相交对数了。(发现没有单调性之后就没想这些了我在干什么啊)
然后但凡这种题都有一个坑爹的事情就是说区间会出现[l,r],其中0<r<l<pi。我们先看没有这种情况怎么做
如果是我这种逗逼的话肯定是会用类似于扫描线的方法扫过去,扫到一个点将以他为右端点的事件删除,以他为左端点的事件加入,更新答案
lyy启发了这么一个思路
线段相交,无非两种情况bzoj 3311 Line of Sight - ydc - ydc的博客
 我们发现,无论是哪种情况,都有恰好两个端点被另一个线段覆盖,于是我们可以计算每个线段覆盖了多少个端点,最后累计并除以2即得到答案
这是一个好的性质……说不定以后还会见到

现在讨论那种绕了一圈再回来的线段,第一思路自然是计算n-未被覆盖的点
这样就行了么?

事实上这样就行了
因为区间长度最多为pi,所以直接这么做看上去分析不够全面,但其实是没有反例了的
于是这题就解决了,最后只能感慨为何我这么逗逼

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 100010
#define eps 1e-10
using namespace std;
typedef long long LL;
const double pi=acos(-1);
int dcmp(double p)
{
if(abs(p)<eps)
return 0;
return p>0?1:-1;
}
struct Point
{
double x,y;
Point() {}
Point(double x,double y): x(x),y(y) {}
friend Point operator - (Point a,Point b)
{
return Point(a.x-b.x,a.y-b.y);
}
void Read()
{
scanf("%lf %lf",&x,&y);
}
}p[maxn],o;
typedef Point Vector;
double Dot(Vector a,Vector b)
{
return a.x*b.x+a.y*b.y;
}
double Len(Vector a)
{
return sqrt(Dot(a,a));
}
double r;
int n;
void read()
{
scanf("%d %lf",&n,&r);
for(int i=1;i<=n;++i)
p[i].Read();
}
void work()
{
static pair<double,double> rad[maxn];
static double R[maxn];
int m=0;
LL ans=0;
for(int i=1;i<=n;++i)
{
double len=Len(p[i]),r1=acos(r/len),r2=atan2(p[i].y,p[i].x);
rad[i]=make_pair(r2-r1,r2+r1);
if(dcmp(rad[i].first+pi)<=0)
rad[i].first=rad[i].first+2*pi;
if(dcmp(rad[i].second-pi)>=0)
rad[i].second=rad[i].second-2*pi;
if(rad[i].first>=rad[i].second&&dcmp(rad[i].first-rad[i].second-pi)<=0)
swap(rad[i].first,rad[i].second);
if(rad[i].first<=rad[i].second&&dcmp(rad[i].second-rad[i].first-pi)>=0)
swap(rad[i].first,rad[i].second);
R[++m]=rad[i].first,R[++m]=rad[i].second;
}
sort(R+1,R+m+1);
for(int i=1;i<=n;++i)
{
int l=lower_bound(R+1,R+m+1,rad[i].first)-R,r=lower_bound(R+1,R+m+1,rad[i].second)-R;
if(l<=r)
ans=ans+r-l-1;
else
ans=ans+m+r-l-1;
}
cout<<ans/2<<endl;
}
int main()
{
read();
work();
return 0;
}


  评论这张
 
阅读(317)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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