欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-03 21:02:55
...

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

题目大意:

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

题解:

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

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

关键在输出字典序最小的方案,方法是这样的,将∠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;
        }
    }
}