bzoj 4660 Crazy Rabbit——LIS解决“相交”限制的思想

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4660

想到一个点可以用它与圆的两个切点表示。并想到可以把切点极角排序，那么就变成环上的一些区间之间的问题。

发现了一个区间和另一个区间可以共存，当且仅当它们相交。不知怎的没看到题面的 “直线” ，以为包含也可以。

所有区间都两两相交，考虑枚举一个点作为所有区间都经过的点。但发现因为是环，可以有区间是首部相交一些区间、尾部相交一些区间的。

然后就不会了。

其实考虑没有那种首部相交一些、尾部相交一些的情况，除了枚举一个所有区间都经过的点，还可以考虑用 LIS 做。

就是枚举一个区间，把 “左端点在自己区间里，与自己是相交关系” 的区间拿出来，按左端点排序，对右端点求 LIS 。

有那种情况的话，考虑把那种区间首尾交换一下，就可以像原来那样做了！！！

求切点极角，令 \( len * cos( s ) = R , len * cos( g ) = x \) ，即 s 是 “该点到原点连线” 与 “切点到原点连线” 的夹角， g 是 “该点到原点连线” 与 “x轴” 的夹角，那么两个切点的极角就是 s-g 和 s+g 。

求 LIS 的时候，把各种点的值改成与当前区间左端点的距离就很方便了。

注意是 “直线” 所以是可以相交但不能包含。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define db double

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

int Mx(int a,int b){return a>b?a:b;}

const int N=; const db pi2=*acos(-);

int n,R,tot,ans;db f[N];

struct Node{

  db l,r;

  Node(db l=,db r=):l(l),r(r) {}

  bool operator< (const Node &b)const

  {return l<b.l;}

}a[N],b[N];

db Dis(int x,int y){return sqrt((db)x*x+(db)y*y);}

bool chk(db x,db l,db r)

{ if(l<r)return x>l&&x<r; else return x>l||x<r;}

db cal(db x,db y)

{ if(x<y)return y-x; else return pi2-(x-y);}

void get(int cr)

{

  sort(b+,b+tot+); int cd=;

  for(int i=;i<=tot;i++)

    {

      if(b[i].r>f[cd])f[++cd]=b[i].r;

      int l=,r=cd,p=;

      while(l<=r)

    {

      int mid=l+r>>;

      if(f[mid]>=b[i].r)p=mid,r=mid-;

      else l=mid+;

    }

      f[p]=b[i].r;

    }

  ans=Mx(ans,cd+);//+1 for i

}

int main()

{

  n=rdn();R=rdn();

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

    {

      int x=rdn(), y=rdn(); db len=Dis(x,y);

      db s=acos(R/len), g=acos(x/len); if(y<)g=pi2-g;

      a[i].l=g-s; a[i].r=g+s;

      if(a[i].l<)a[i].l+=pi2; if(a[i].r>pi2)a[i].r-=pi2;

    }

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

    {

      tot=;

      for(int j=;j<=n;j++)

    {

      if(j==i)continue;

      if(chk(a[j].l,a[i].l,a[i].r)&&!chk(a[j].r,a[i].l,a[i].r))

        b[++tot]=Node(cal(a[i].l,a[j].l),cal(a[i].l,a[j].r));

      else if(chk(a[j].r,a[i].l,a[i].r)&&!chk(a[j].l,a[i].l,a[i].r))

        b[++tot]=Node(cal(a[i].l,a[j].r),cal(a[i].l,a[j].l));

    }

      get(i);

    }

  printf("%d\n",ans);

  return ;

}