题意:第一象限有n个点,你从x正半轴任选一个位置出发,vy恒定,vx可以任意变化,不过只能在-vy/r到vy/r之间变化,问你最多能经过多少个点。

暴力dp是n^2,不可取。

注意到,一个点,所能到达它的点,是它后面一个张角内的所有点。这个张角很容易算出。

于是可以将这些点全部映射到一个新的坐标系内,使得这个坐标系内每个点左下方的点都是能到达它的点。(没必要真的算出那些真的变换后的坐标,可以以到那个虚拟张角的两条边的距离作为坐标,这样虽然扭曲了一点,但不影响答案。)

于是转化成了二维偏序问题,可以用一维排序+一维线段树维护左下方的最大值来解决。

注意是实数点,离散化的时候要处理好误差。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=0.0000001;
struct Point{
double x,y;
Point(const double &x,const double &y){
this->x=x;
this->y=y;
}
Point(){}
void read(){
scanf("%lf%lf",&x,&y);
}
double length(){
return sqrt(x*x+y*y);
}
}a[100005];
typedef Point Vector;
Vector operator - (const Point &a,const Point &b){
return Vector(a.x-b.x,a.y-b.y);
}
double Cross(const Vector &a,const Vector &b){
return a.x*b.y-a.y*b.x;
}
double DisToLine(Point P,Point A,Point B)
{
Vector v1=B-A,v2=P-A;
return fabs(Cross(v1,v2))/v1.length();
}
int n,r,w,h;
pair<double,int> b[100005];
struct data{
double v;
int p;
data(const double &v,const int &p){
this->v=v;
this->p=p;
}
data(){}
}t[100005];
bool cmp(const data &a,const data &b){
return a.v<b.v;
}
bool cm2(const pair<double,int> &a,const pair<double,int> &b){
return a.second<b.second;
}
int ans;
int maxv[100005<<2];
void update(int p,int v,int rt,int l,int r){
if(l==r){
maxv[rt]=v;
return;
}
int m=(l+r>>1);
if(p<=m){
update(p,v,rt<<1,l,m);
}
else{
update(p,v,rt<<1|1,m+1,r);
}
maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);
}
int query(int ql,int qr,int rt,int l,int r){
if(ql<=l && r<=qr){
return maxv[rt];
}
int m=(l+r>>1),res=0;
if(ql<=m){
res=max(res,query(ql,qr,rt<<1,l,m));
}
if(m<qr){
res=max(res,query(ql,qr,rt<<1|1,m+1,r));
}
return res;
}
int main(){
//freopen("g.in","r",stdin);
scanf("%d%d%d%d",&n,&r,&w,&h);
Point p=Point((double)w*0.5,-(double)w*(double)r*0.5);
Point q=Point((double)w,0.0);
Point yd=Point(0.0,0.0);
for(int i=1;i<=n;++i){
a[i].read();
double d1=DisToLine(a[i],p,q);
double d2=DisToLine(a[i],p,yd);
a[i]=Point(d1,d2);
b[i].first=d1;
t[i].v=d2;
t[i].p=i;
}
sort(t+1,t+n+1,cmp);
int zy=0;
b[t[1].p].second=++zy;
for(int i=2;i<=n;++i){
if(fabs(t[i].v-t[i-1].v)>eps){
++zy;
}
b[t[i].p].second=zy;
}
int sta;
sort(b+1,b+n+1);
for(int i=1;i<=n;++i){
if(i==1 || fabs(b[i].first-b[i-1].first)>eps){
sta=i;
}
if(i==n || fabs(b[i].first-b[i+1].first)>eps){
sort(b+sta,b+i+1,cm2);
for(int j=sta;j<=i;++j){
int x=query(1,b[j].second,1,1,zy);
ans=max(ans,x+1);
update(b[j].second,x+1,1,1,zy);
}
}
}
printf("%d\n",ans);
return 0;
}

最新文章

  1. Java编程中-servlet
  2. python中引用
  3. C# dll加载,抽象方法的使用
  4. CVE: 2014-6271、CVE: 2014-7169 Bash Specially-crafted Environment Variables Code Injection Vulnerability Analysis
  5. openal-1.13 静态编译(mingw32)
  6. css问题 ie7兼容性问题
  7. 转储指定的数据块并查看TRC信息
  8. iis 回收工作进程时出错的解决办法
  9. web前端笔记整理---CSS
  10. POJ3468(线段树 区间修改 lazy-tag)
  11. JS报表打印分页CSS
  12. java web 在线聊天的基本实现
  13. 单片机成长之路(51基础篇) - 008 C51 的标示符和关键字
  14. Asp.net core 学习笔记 ( ViewComponent 组件 )
  15. 【基础练习】【拓扑排序】codevs3294 车站分级题解
  16. JS貪食蛇網頁代碼
  17. Laravel 程序架构设计思路:使用动作类
  18. 深层神经网络框架的python实现
  19. HDU 2114 Calculate S(n)
  20. Java递归删除文件目录的方法

热门文章

  1. iOS程序启动原理---iOS-Apple苹果官方文档翻译
  2. 【洛谷 P4219】 [BJOI2014]大融合(LCT)
  3. Android 搭建Linux系统
  4. layui利用jQuery设置下拉列表的值
  5. Java并发编程(二)
  6. 85.Maximal Rectangle---dp
  7. openjudge-NOI 2.6-1996 登山
  8. Freemaker如何遍历key为non-string类型的map?
  9. CentOS7.4 安装 oracle12c
  10. centos 下单独安装mysql