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

ydc的博客

 
 
 

日志

 
 

bzoj 2732 (hnoi2012)射箭(不完美) 中间怎么漏了一篇  

2013-02-10 18:17:40|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

裸的半平面交

对于一个靶子,我们可以得到两个不等式

题目就是有若干个不等式组,每个不等式组至多含有x,y这两个变量

所以半平面交可做

当然还要二分一下

也就是二分答案,把1到当前答案的半平面都存下来然后判一下

但我的程序超时了

用的方法就是刘汝佳在白书上的方法,常数应该不是很大才对

反正就是超时了,可见那个方法不是最优的。

反正我的代码跟他的应该差别不大

然后就是注意事项

一、精度卡的很严重,最好开1e-16,否则极有可能挂

二、如果是抄的刘汝佳的代码,有个地方要改一下,就是判两条象征着半平面的直线是否共线不要用叉积,用它们的atan2函数判

在bzoj上还是过了的

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define eps 1e-16
#define MAXN 200010
using namespace std;
int dcmp(double p)
{
    if(fabs(p)<eps)  return 0;
    return p>eps?1:-1;
}
struct Point
{
    double x,y;
    Point() {}
    Point(double x,double y): x(x),y(y) {}
    friend Point operator + (const Point &a,const Point &b){  return Point(a.x+b.x,a.y+b.y);  }
    friend Point operator - (const Point &a,const Point &b){  return Point(a.x-b.x,a.y-b.y);  }
    friend Point operator * (const Point &a,double p){  return Point(a.x*p,a.y*p);  }
}inter[MAXN];
typedef Point Vector;
double Cross(const Vector &a,const Vector &b){  return a.x*b.y-a.y*b.x;  }
struct Line
{
    Point p;
    Vector v;
    double rad;
    Line() {}
    Line(const Point &p,const Vector &v): p(p),v(v)  {  rad=atan2(v.y,v.x);  }
    friend bool operator < (const Line &a,const Line &b){  return dcmp(a.rad-b.rad)<0;  }
}L[MAXN],temp[MAXN],queue[MAXN];
bool Left(const Point &a,const Line &b){  return dcmp(Cross(a-b.p,b.v))<=0;  }
Point getinter(const Line &a,const Line &b)
{
    Vector u=a.p-b.p;
    double t=Cross(b.v,u)/Cross(a.v,b.v);
    return a.p+a.v*t;
}
int n,tot;
void read()
{
    scanf("%d",&n);
    double x,a,b;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf %lf %lf",&x,&a,&b);
        L[++tot]=Line(Point(0,a/x),Vector(1,-x)),L[++tot]=Line(Point(0,b/x),Vector(-1,x));
    }
}
bool halfplane(int n)
{
    sort(temp+1,temp+n+1);
    int front=1,rear=1;
    queue[rear]=temp[1];
    for(int i=2;i<=n;i++)
    {
        while(front<rear&&!Left(inter[rear-1],temp[i]))  rear--;
        while(front<rear&&!Left(inter[front],temp[i]))  front++;
        queue[++rear]=temp[i];
        if(!dcmp(queue[rear-1].rad-temp[i].rad)&&Left(temp[i].p,queue[--rear]))  queue[rear]=temp[i];
        if(front<rear)  inter[rear-1]=getinter(queue[rear-1],queue[rear]);
    }
    while(front<rear&&!Left(inter[rear-1],queue[front]))  rear--;
    return rear-front>1;
}
bool check(int mid)
{
    for(int i=1;i<=mid*2;i++)
        temp[i]=L[i];
    return halfplane(mid*2);
}
int Two(int l,int r)
{
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(mid)==true)  l=mid+1;
        else r=mid;
    }
    return l-1;
}
int main()
{
    read();
    printf("%d\n",Two(1,n));
    return 0;
}


  评论这张
 
阅读(620)| 评论(7)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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