CF682E Alyona and Triangles

题目链接

解题思路

比较显然的是一定从“最大三角形面积不超过$S$”这一点来入手。

如上图，如果$A,B,C$三点构成的是面积最大的三角形，我们就可以知道，$C$是到直线$AB$最远的点。所以不可能有点在过点$C$平行与$AB$的直线外面。同样的，另外$3$点也有类似的结论。所以所有的点都应该在图中最大的三角形上及内部。

然后这个大三角形恰好又是面积最大三角形面积的$4$倍，这样问题就得到了解决。

至于如何求面积最大的三角形，就直接求一个凸包，枚举两个点，用类似于旋转卡壳的手段求面积即可。时间复杂度$O(n^2)$。

参考程序

#include <cstdio>
#include <cmath>
#include <algorithm>
#define LD long double
using namespace std;

const int Maxn = 5010;
const LD Eps = 1e-12;

LD sqr( LD x ) { return x * x; }
int Compare( LD x, LD y ) {
    if( fabs( x - y ) <= Eps ) return 0;
    if( x > y ) return 1; else return -1;
}
struct point {
    LD x, y;
    point operator + ( const point Other ) const { return ( point ) { Other.x + x, Other.y + y }; }
    point operator - ( const point Other ) const { return ( point ) { x - Other.x, y - Other.y }; }
    LD operator * ( const point Other ) const { return y * Other.x - x * Other.y; }
    LD operator / ( const point Other ) const { return sqrt( sqr( Other.x - x ) + sqr( Other.y - y ) ); }
    bool operator < ( const point Other ) const { return Compare( y, Other.y ) == -1 || ( Compare( y, Other.y ) == 0 && Compare( x, Other.x ) == -1 ); }
    bool operator == ( const point Other ) const { return Compare( x, Other.x ) == 0 && Compare( y, Other.y ) == 0; }
};

int N;
LD S;
point A[ Maxn << 1 ];
int Stack[ Maxn ];
int T1, T2, T3;
LD MaxArea;

bool Comperation1( point x, point y ) { return x < y; }
bool Comperation2( point x, point y ) { return Compare( ( x - A[ 1 ] ) * ( y - A[ 1 ] ), 0.0 ) == -1; }
void ConvexHull() {
    sort( A + 1, A + N + 1, Comperation1 ); sort( A + 2, A + N + 1, Comperation2 );
    Stack[ 0 ] = 2; Stack[ 1 ] = 1; Stack[ 2 ] = 2;
    for( int i = 3; i <= N; ++i ) {
        for( ; Stack[ 0 ] > 1 && Compare( ( A[ Stack[ Stack[ 0 ] ] ] - A[ Stack[ Stack[ 0 ] - 1 ] ] ) * ( A[ i ] - A[ Stack[ Stack[ 0 ] - 1 ]  ] ), 0.0 ) == 1; --Stack[ 0 ] );
        Stack[ ++Stack[ 0 ] ] = i;
    }
    for( int i = 1; i <= N; ++i ) A[ i ] = A[ Stack[ i ] ]; N = Stack[ 0 ];
    return;
}
void GetMaxArea() {
    for( int i = N + 1; i <= N * 2; ++i ) A[ i ] = A[ i - N ];
    MaxArea = 0.0;
    for( int i = 1; i < N - 1; ++i ) {
        int Top = i + 2;
        for( int j = i + 1; j < N; ++j ) {
            for( ; Compare( ( A[ j ] - A[ i ] ) * ( A[ Top ] - A[ Top - 1 ] ), 0.0 ) * Compare( ( A[ j ] - A[ i ] ) * ( A[ Top + 1 ] - A[ Top ] ), 0.0 ) > 0; ) ++Top;
            LD Area = ( A[ j ] - A[ i ] ) * ( A[ Top ] - A[ i ] );
            Area = fabs( Area ) * 0.5;
            if( Compare( Area, MaxArea ) == 1 ) {
                MaxArea = Area;
                T1 = i; T2 = j; T3 = Top;
            }
        }
    }
    return;
}
int main() {
    scanf( "%d%Lf", &N, &S );
    for( int i = 1; i <= N; ++i ) scanf( "%Lf%Lf", &A[ i ].x, &A[ i ].y );
    ConvexHull();
    GetMaxArea();
    point Ans1 = A[ T1 ] + ( A[ T2 ] - A[ T3 ] );
    point Ans2 = A[ T1 ] - ( A[ T2 ] - A[ T3 ] );
    point Ans3 = A[ T2 ] + ( A[ T1 ] - A[ T3 ] );
    if( Ans3 == Ans2 || Ans3 == Ans1 ) Ans3 = A[ T2 ] - ( A[ T1 ] - A[ T3 ] );
    printf( "%d %d\n", ( int )Ans1.x, ( int )Ans1.y );
    printf( "%d %d\n", ( int )Ans2.x, ( int )Ans2.y );
    printf( "%d %d\n", ( int )Ans3.x, ( int )Ans3.y );
    return 0;
}