『HGOI 20190917』Cruise 题解 (计算几何+DP)

分手后的思念是犯贱 2023-06-05 11:27 57阅读 0赞

**题目概述**

> 在平面直角坐标系的第$1$象限和第$4$象限有$n$个点，其中第$i$个点的坐标为$(x\_i,y\_i)$,有一个权值$p\_i$
> 
> 从原点$O(0,0)$出发，不重复的经过一些点，最终走到原点,围成一个多边形。我们定义开心程度为$f$。
> 
> 设经过节点总共走的路径长度是$s$，最终路径围成的多边形中所有点的权值和为$w$，则$f = \\frac\{w\}\{s\}$。
> 
> 试最大化开心程度$f$。保留$3$位小数后输出$f\_\{min\}$。
> 
> 对于$100\\%$的数据满足$n\\leq 2\\times 10^3 , 0 \\leq x\_i \\leq 10^4 , |y\_i| \\leq 10^4 , 1\\leq p\_i \\leq 10^4$

**Solution - 前置知识**

本题考场由@ljc20020730胡出正解。涉及部分计算几何知识。

首先，我们需要知道**向量叉积**的计算方法和几何含义。

> 定义向量$\\vec\{a\}$ 和 $\\vec\{b\}$，则记向量叉积为$\\vec\{a\} \\times \\vec\{b\}$

设向量坐标 $\\vec\{a\} = (x\_a,y\_a) , \\vec\{b\} = (x\_b,y\_b)$

其中，叉积的几何意义是一个垂直于$| \\vec\{a\} $与$\\vec\{b\}$构成平面的向量$c$，其模长$| \\vec\{a\} \\times \\vec\{b\} | = |x\_a y\_b - x\_by\_a| $

其方向可以用右手螺旋定则确定（即右手四指从$\\vec\{a\}$指向$\\vec\{b\}$，大拇指所在方向就是叉积后向量方向）

于是，设点$A,B,C$，则可以使用向量叉积方便的判断点$A$在直线$BC$的左侧还是右侧。

> 若$|\\vec\{BA\} \\times \\vec\{BC\}| > 0$则在直线$BC$的左侧；
> 
> 若$|\\vec\{BA\} \\times \\vec\{BC\}| = 0$在直线$BC$上；
> 
> 若$|\\vec\{BA\} \\times \\vec\{BC\}| < 0$则在直线$BC$的右侧；

这样，我们就可以判断$P$是否在由$A,B,C$构成的三角形内了。

> $P,A$必须在直线$BC$的同侧，$P,B$必须在直线$AC$的同侧，$P,C$必须在直线$AB$的同侧。

其次，我们还需要知道利用向量叉积进行**极角排序**的相关知识点。

极角：设坐标轴$Ox$并规定逆时针为正方向，对任何点其到原点构成直线与坐标轴的夹角叫极角。

显然，理论上，如果计算机非常准确，则极角排序可以使用反三角函数解决。

对于两个点$(x\_1,y\_1), (x\_2,y\_2)$如果$(x\_2,y\_2)$在原点和$(x\_1,y\_1)$构成直线的右侧，则需要交换这两个点的顺序。

这可以利用之前点在直线方向判定的叉积来实现。利用快速排序，可以做到$O(n \\log\_2 n)$

**Solution 关于本题**

**　**首先，答案具有单调性，我们可以二分快乐值$f$，现在问题是判定是否能找出一条方案，使得其快乐值大于二分的答案。

记$\\frac\{w\}\{s\} \\geq f$由于$s > 0$则$w - fs \\geq 0$，对于每次二分的定值$f$，最大化$w - fs$的值即可。

我们首先会想到由于$w$是围成图形内包含点的权值和，我们首先按照$O(0,0)$进行极角排序。按照此时的顺序进行$DP$

状态为$f\[i\]$表示最后一个经过点$i$的路径答案，显然$f\[i\] = max \\\{ f\[j\] + cost(i,j) \\\}$其中$cost(i,j)$表示极角排序后$i$点(不包含)到$j$点(包含)的元素的权值和。

如果暴力计算$cost(i,j)$，时间复杂度是$O(n^3 log\_2 n)$。我们必须离线处理$cost(i,j)$的值。

首先，对极角排序后的$n$个点编成连续的编号$1- n$，设当前点是$i$，则将$i+1 - n$号点的权值，单点插入到树状数组对应编号位中，便于区间查询。

这些插入的点对第$i$个点为基准进行极角排序(角相同则按照半径大优先)，依次考虑。设当前考虑到点$j$。

为了计算$cost(i,j)$，我们需要知道，树状数组区间中i的编号到j的编号之间的答案和。

可以证明，经过这两次极角排序后，i的编号到j的编号之间的点$k$，在以$i$和$j$和$O(0,0)$构成的三角形中了。

然后，由于该点在后续的点将不再会被用到，故在树状数组中单点删除即可。

于是，我们可以在$O(n^2 log\_2 n)$的复杂度为维护$cost(i,j)$了。

对于$DP$的转移也就变成$O(1)$的了。

本题最终时间复杂度是$O(n^2 \\log\_2 n)$

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

# pragma GCC optimize(3)
    # include <bits/stdc++.h>
    using namespace std;
    const int N=2e3+10;
    int n,g[N][N],c[N];
    inline int read()
    {
        int X=0,w=0; char c=0;
        while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
        while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
        return w?-X:X;
    }
    # define lowbit(x) (x&(-x))
    void update(int x,int d) { for (;x<=n;x+=lowbit(x)) c[x]+=d;}
    int query(int x) { int ret=0; for (;x;x-=lowbit(x)) ret+=c[x]; return ret;}
    int query(int l,int r) {
         return query(r)-query(l-1);}
    struct rec{ int x,y,p; }a[N],b[N],tmp[N];
    int cross(rec a,rec b) { return a.y*b.x-a.x*b.y;}
    int direct (rec a,rec b,rec c) {
        rec ba={a.x-b.x,a.y-b.y,0};
        rec bc={c.x-b.x,c.y-b.y,0};
        int ret=cross(ba,bc);
        if (ret==0) return 0;
        else if (ret<0) return -1;
        else if (ret>0) return 1;
    }
    bool triangle(rec p,rec a,rec b,rec c) {
        if (direct(p,b,c)*direct(a,b,c)<0) return false;
        if (direct(p,a,c)*direct(b,a,c)<0) return false;
        if (direct(p,a,b)*direct(c,a,b)<0) return false;
        return true;
    }
    bool cmp1(rec a,rec b) {
        return (direct(b,{
         0,0,0},a)>0);
    }
    bool operator == (rec a,rec b) {
        return a.x==b.x && a.y==b.y && a.p==b.p;
    }
    int cx,cy;
    bool cmp2(rec a,rec b) {
        int ret=direct(b,(rec){cx,cy,0},a);
        if (ret) return ret>0;
        return (a.x-cx)*(a.x-cx)+(a.y-cy)*(a.y-cy) > (b.x-cx)*(b.x-cx)+(b.y-cy)*(b.y-cy);
    }
    double dist(int i,int j) {
        return sqrt((a[j].y-a[i].y)*(a[j].y-a[i].y) + (a[j].x-a[i].x)*(a[j].x-a[i].x));
    }
    double f[N];
    bool check(double mid) {
        for (int i=1;i<=n;i++) 
            f[i]=a[i].p-mid*dist(0,i);
        for (int i=1;i<n;i++) 
         for (int j=i+1;j<=n;j++) 
            f[j]=max(f[j],f[i]+g[i][j]-mid*dist(i,j));
        double ans=-1e9;
        for (int i=1;i<=n;i++) ans=max(ans,f[i]-dist(i,0)*mid);
        return ans>0;
    }
    int main() {
        n=read(); a[0].x=a[0].y=0;
        for (int i=1;i<=n;i++) 
            a[i].x=read(),a[i].y=read(),a[i].p=read();
        sort(a+1,a+1+n,cmp1);
        memcpy(b,a,sizeof(a)); 
        for (int i=1;i<=n;i++) b[i].p=i;
        for (int i=1;i<=n;i++) {
            memset(c,0,sizeof(c));
            int cnt=0;
            for (int j=i+1;j<=n;j++) {
                tmp[++cnt]=b[j];
                update(j,a[j].p); 
            }
            cx=a[i].x; cy=a[i].y;
            sort(tmp+1,tmp+1+cnt,cmp2);
            for (int j=1;j<=cnt;j++) {
                g[i][tmp[j].p]=query(i,tmp[j].p);
                update(tmp[j].p,-a[tmp[j].p].p);
            }
        }
        double l=0,r=2e7,ans;
        while (r-l>1e-5) {
            double mid=(l+r)/2.0;
            if (check(mid)) ans=mid,l=mid;
            else r=mid;
        }
        printf("%.3lf\n",ans);
        return 0;
    }

cruise.cpp

转载于:https://www.cnblogs.com/ljc20020730/p/11544341.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/06ae372f1bf34711ac62ab4ebb8a1757.png