Nested Triangles 2018 ACM-ICPC中国大学生程序设计竞赛

题目链接：https://nanti.jisuanke.com/t/28410

题目大意：

给出n个点，和两个点P，Q，求一个最大的集合，使得集合中的点与P、Q两点围成的三角形是层层包含的，若有多种最大数目的方案，输出字典序最小的。

题解：

设n个点为点c[i]，首先将n个点依据直线PQ的两侧分为两部分，对每一部分，将∠c[i]PQ从小到大排序，再对∠c[i]QP求最长上升子序列就可求出最大的数目。如图：

关键在输出字典序最小的方案，方法是这样的，将∠c[i]PQ从小到大排序后，然后从后往前，求以点c[i]为起点的最长下降子序列的长度，方法为正着求最长上升子序列。假设整体的最长下降子序列长度为len，那么首先在以某些点为起点的最长下降子序列长为len中取一个id最小的，然后在长为len-1中取一个满足包含关系且id最小的，以此类推。

以上为思路，实现起来有些变化，如果真的按角度来做，会有很大的精度问题。我们将角的大小关系转变为向量的叉积，看图发现∠c[3]PQ大于∠c[4]PQ，那么一定有向量pc[3]叉乘向量pc[4]小于0，由于叉积为整数，这样就消除了精度的问题。

代码：

#include<bits/stdc++.h>
#define N 100310
#define LL long long
using namespace std;
struct Point
{
    LL x,y;
    Point(LL x=0,LL y=0):x(x),y(y){ }
};

typedef Point Vector;
Vector operator - (Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
LL Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}

Point a[N],c[N],g[N],p,q;
vector<int>v[N];
int c1[N],c2[N];
struct rr
{
    Point c;
    int id;
}w[N];

int spy(int l,int r,Point x)
{
    while (l-r<0)
    {
        int t=(l+r)>>1;
        if (Cross(x-q,g[t]-q)==0) return t;
        if (Cross(g[t]-q,x-q)<0)l=t+1;else r=t;
    }
    return l;
}
int spy1(int l,int r,Point x)
{
    while (l-r<0)
    {
        int t=(l+r)>>1;
        if (Cross(x-q,g[t]-q)==0) return t;
        if (Cross(g[t]-q,x-q)>0)l=t+1;else r=t;
    }
    return l;
}
bool cmp(const rr a,const rr b)
{
   return  Cross(a.c-p,b.c-p)>0|| Cross(a.c-p,b.c-p)==0 && Cross(a.c-q,b.c-q)>0;
}

bool cmp1(const rr a,const rr b)
{
   return  Cross(a.c-p,b.c-p)<0|| Cross(a.c-p,b.c-p)==0 && Cross(a.c-q,b.c-q)<0;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("02","r",stdin);    freopen("1.txt","w",stdout);
    int T,TT=0;
    cin>>T;
    while(T--)
    {
        cin>>p.x>>p.y>>q.x>>q.y;
        int n,m;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>c[i].x>>c[i].y;
        for (int i=1;i<=n;i++)c1[i]=c2[i]=0;
        m=0;
        for(int i=1;i<=n;i++) if ((Cross(q-p,c[i]-p))>0)  w[++m]=rr{c[i],i};

        sort(w+1,w+m+1,cmp);
        for (int i=1;i<=n;i++) v[i].clear();
        v[1].emplace_back(1);
        g[1]=w[1].c;int ff=1;
        for (int i=2;i<=m;i++)
        {
            int j=spy(1,ff+1,w[i].c);
            g[j]=w[i].c;
            if (j==ff+1) ff++;
            v[j].emplace_back(i);
        }
        for (int j=0;j<v[ff].size();j++) if (j==0 || (j>0 && w[v[ff][j]].id<w[c1[ff]].id)) c1[ff]=v[ff][j];

        for (int i=ff-1;i>0;i--)
        {
            for (int j=0;j<v[i].size();j++) if((Cross(w[v[i][j]].c-p,w[c1[i+1]].c-p))>0 &&
            (Cross(w[v[i][j]].c-q,w[c1[i+1]].c-q))<0 ) if (c1[i]==0 || w[v[i][j]].id<w[c1[i]].id)
            c1[i]=v[i][j];
        }
        for (int i=ff;i>0;i--) c1[i]=w[c1[i]].id; int tt=ff;

        m=0;
        for(int i=1;i<=n;i++) if ((Cross(q-p,c[i]-p))<0)            w[++m]=rr{c[i],i};

        sort(w+1,w+m+1,cmp1);
        for (int i=1;i<=n;i++) v[i].clear();
        v[1].emplace_back(1);
        g[1]=w[1].c;ff=1;
        for (int i=2;i<=m;i++)
        {
            int j=spy1(1,ff+1,w[i].c);
            g[j]=w[i].c;
            if (j==ff+1) ff++;
            v[j].emplace_back(i);
        }
        for (int j=0;j<v[ff].size();j++) if (j==0 || (j>0 && w[v[ff][j]].id<w[c2[ff]].id)) c2[ff]=v[ff][j];

        for (int i=ff-1;i>0;i--)
        {
            for (int j=0;j<v[i].size();j++) if((Cross(w[v[i][j]].c-p,w[c2[i+1]].c-p))<0 &&
            (Cross(w[v[i][j]].c-q,w[c2[i+1]].c-q))>0 ) if (c2[i]==0 || w[v[i][j]].id<w[c2[i]].id)
            c2[i]=v[i][j];
        }
        for (int i=ff;i>0;i--) c2[i]=w[c2[i]].id;

        if (tt<ff || (tt==ff && c1[tt]>c2[tt]))
        {
            cout<<"Case #"<<++TT<<": "<<ff<<endl;
            for (int i=ff;i>0;i--) cout<<c2[i]<<endl;
        }else
        {
            cout<<"Case #"<<++TT<<": "<<tt<<endl;
            for (int i=tt;i>0;i--) cout<<c1[i]<<endl;
        }
    }
}