CF605C Freelancer's Dreams

题目链接

解题思路1

把这个问题放到平面上。考虑如果总量为$1$能组成哪些$p$和$q$。那么两个点能组成的就是由这两个点为端点的线段。同理，三个点就是三角形，多个点就是这些点的凸包为边界的多边形。

于是我们只需要求经过点$(p,q)$的射线与凸包的交点。如果有多个，则取到原点距离较长的那一段。那么答案就是点$(p,q)$到原点的距离比上交点到原点的距离。

如果没有交点，那么说明我们无法构造出恰好为$(p,q)$的方案。那么我们加入两个点$(man_x,0)$与$(0,max_y)$，剩下做法同上这样就可以了。

解题思路2

由于问题是在平面内，所以由于线性关系，我们最多选择两种。这点通过上面那种做法也可以看出。那么做出凸包后用两个指针扫一遍也是可以的。然而并没有具体实现过

参考程序

思路1的程序

#include<bits/stdc++.h>
#define LD long double
using namespace std;

const LD Eps = 1e-12;
const int Maxn = 100010;
int N;
struct point {
    LD x, y;
};
LD p, q;
point A[ Maxn ];
int Appear[ Maxn ];
int Stack[ Maxn ];

int Compare( LD x, LD y ) {
    if( fabs( x - y ) <= Eps ) return 0;
    if( x > y ) return 1; else return -1;
}

void Init() {
    scanf( "%d%Lf%Lf", &N, &p, &q );
    for( int i = 1; i <= N; ++i ) scanf( "%Lf%Lf", &A[ i ].x, &A[ i ].y );
    A[ N + 1 ].x = 0;
    for( int i = 1; i <= N; ++i ) 
        if( Compare( A[ i ].y, A[ N + 1 ].y ) == 1 ) 
            A[ N + 1 ].y = A[ i ].y;
    ++N;
    A[ N + 1 ].y = 0;
    for( int i = 1; i <= N; ++i ) 
        if( Compare( A[ i ].x, A[ N + 1 ].x ) == 1 ) 
            A[ N + 1 ].x = A[ i ].x;
    ++N;
    return;
}

bool Cmp( point x, point y ) {
    return Compare( x.x * y.y - x.y * y.x, 0.0 ) == 1;
}

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

LD Cross( int x, int y, int z ) {
    return ( A[ x ].x - A[ z ].x ) * ( A[ y ].y - A[ z ].y ) - ( A[ x ].y - A[ z ].y ) * ( A[ y ].x - A[ z ].x );
}

void TuBao() {
    Stack[ 0 ] = 2;
    Stack[ 1 ] = 1; Stack[ 2 ] = 2;
    for( int i = 3; i <= N; ++i ) {
        while( Compare( Cross( i, Stack[ Stack[ 0 ] ], Stack[ Stack[ 0 ] - 1 ] ), 0.0 ) >= 0 && Stack[ 0 ] >= 2 ) --Stack[ 0 ];
        Stack[ ++Stack[ 0 ] ] = i;
    }
    return;
}

int main() {
    Init();
    sort( A + 1, A + N + 1, Cmp );
    TuBao();
    N = Stack[ 0 ];
    for( int i = 1; i <= N; ++i ) A[ i ] = A[ Stack[ i ] ];
    for( int i = 2; i < N; ++i ) 
        if( Compare( A[ i ].x / A[ i ].y, p / q ) == 0 ) {
            printf( "%.10Lf\n", Dis( p, q ) / Dis( A[ i ].x, A[ i ].y ) );
            exit( 0 );
        }
    for( int i = 1; i < N; ++i ) 
        if( Compare( A[ i ].x * q - A[ i ].y * p, 0.0 ) * Compare( A[ i + 1 ].x * q - A[ i + 1 ].y * p, 0.0 ) < 0 ) {
            if( Compare( A[ i ].x, A[ i + 1 ].x ) == 0 ) {
                printf( "%.10Lf\n", p / A[ i ].x );
                break;
            }
            LD T1, T2;
            T1 = A[ i ].y - ( A[ i ].y - A[ i + 1 ].y ) / ( A[ i ].x - A[ i + 1 ].x ) * A[ i ].x;
            T2 = q / p - ( A[ i ].y - A[ i + 1 ].y ) / ( A[ i ].x - A[ i + 1 ].x );
            LD X = T1 / T2;
            LD Y = X * q / p;
            printf( "%.10Lf\n", Dis( p, q ) / Dis( X, Y ) );
            break;
        }
    return 0;
}

最后的问题

程序中求凸包部分，如果判出三点共线的情况，那么需要删除中间那个点才可以，不然会Wrong Answer On Test 12。不知为何。