Тема: Convex Hull

Собственно, условие:

You are given several points on the plain. Find their convex hull.

Input
The first line of the input file contains n - the number of points (3<=n<=200000).
The following n lines describe points. Each point is described by two integer
numbers - its coordinates. Coordinates do not exceed 10^9 by their absolute
values. There three points that are not on the same line. There can be equal points.

Output
The first line of the output file must contain the number of vertices in the
convex hull. The second line must contain numbers of points that are vertices
of the convex hull in its cointercloclwise traversal. No two edges of the hull
must be on the same line.
The third line must contain the length of the perimetr of the hull. The fourth
line must contain the area of the hull. These two numbers must be accurate up to
10^-6

Examples

convex.in

9
0 0
1 1
2 2
1 0
0  1
2 0
0 2
2 1
1 2

convex.out

4
1 6 3 7
8.0
4.0

Привожу здесь же мой код, который в таком виде получает WA 8:

#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
#include<cmath>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pt;
typedef vector<pt> vpii;

#define x first
#define y second
#define mp make_pair
#define pb push_back

int n;
vpii v;
vector<int> ans;

int cw( pt & p1, pt & p2, pt & p3 ) {
    return (
            ( p1.y + p2.y ) * ( p2.x - p1.x ) + 
            ( p2.y + p3.y ) * ( p3.x - p2.x ) +
            ( p1.y + p3.y ) * ( p1.x - p3.x )
            ) >= 0;
}
int ccw( pt & p1, pt & p2, pt & p3 ) {
    return (
            ( p1.y + p2.y ) * ( p2.x - p1.x ) + 
            ( p2.y + p3.y ) * ( p3.x - p2.x ) +
            ( p1.y + p3.y ) * ( p1.x - p3.x )
            ) <= 0;
}
void out( vpii & v ) {
    for( int i = 0; i < 15; ++i )
        cerr << "-";
    cerr << endl;
    for( int i = 0; i < v.size(); ++i )
        cerr << v[ i ].x << " " << v[ i ].y << endl; 
    for( int i = 0; i < 15; ++i )
            cerr << "-";
        cerr << endl;
} 
int cmp( int a, int b ) {
    return v[ a ] < v[ b ];
}
vpii convex_hull( vpii v ) {
    vector<int> vec;
    for( int i = 0; i < v.size(); ++i )
        vec.pb( i );
    sort( vec.begin(), vec. end(), cmp );
    //out( v );
    pt p1 = v[ vec[ 0 ] ];
    pt p2 = v[ vec[ vec.size() - 1 ] ];
    vpii up, down;
    down.pb( p1 );
    up.pb( p1 );
    vector<int> d, u;
    d.pb( vec[ 0 ] );
    u.pb( vec[ 0 ] );
    for( int i = 1; i < v.size(); ++i ) {
        if( i == v.size() - 1 || cw( p1, v[ vec[ i ] ], p2 ) ) {
            while( up.size() > 1 && ccw( up[ up.size() - 2 ], up[ up.size() - 1 ], v[ vec[ i ] ] ) )
                up.pop_back(),
                u.pop_back();
            up.pb( v[ vec[ i ] ] );
            u.pb( vec[ i ] );
        }
        if( i == v.size() - 1 || ccw( p1, v[ vec[ i ] ], p2 ) ) {
            while( down.size() > 1 && cw( down[ down.size() - 2 ], down[ down.size() - 1 ], v[ vec[ i ] ] ) )
                down.pop_back(),
                d.pop_back();
            down.pb( v[ vec[ i ] ] );
            d.pb( vec[ i ] );
        }
    }
    vpii res;
    for( int i = 0; i < down.size(); ++i )
        res.pb( down[ i ] ),
        ans.pb( d[ i ] );
    for( int i = up.size() - 2; i > 0; --i )
        res.pb( up[ i ] ),
        ans.pb( u[ i ] );
    //out( res );
    return res;
}
double dist( pt & p1, pt & p2 ) {
    return sqrt( ( double )( p1.x - p2.x ) * ( p1.x - p2.x ) +
            ( p1.y - p2.y ) * ( p1.y - p2.y) );
}
ll square( pt & p1, pt & p2 ) {
    return ( p1.y + p2.y ) * ( p2.x - p1.x );
}
int main() {
    freopen( "convex.in", "r", stdin );
    freopen( "convex.out", "w", stdout ); 
    cin >> n;
    v.resize( n );
    for( int i = 0; i < n; ++i )
        cin >> v[ i ].x >> v[ i ].y;
    v = convex_hull( v );
    //out( v );
    cout << v.size() << endl;
    for( int i = 0; i < v.size(); ++i ) 
        cout << ans[ i ] + 1 << " ";
    double per = 0.0;
    ll sq = 0;
    for( int i = 0; i < v.size(); ++i ) {
        int j = ( i + 1 ) % v.size();
        per += dist( v[ i ], v[ j ] );
        sq += square( v[ i ], v[ j ] );
    }
    sq = abs( sq );
    cout.precision( 7 );
    cout << fixed << endl << per << endl;// << -double( sq ) / 2.0 << endl;
    if( sq & 1 )
        cout << sq / 2 << ".500000";
    else cout << sq / 2 << ".000000";
    return 0;
}

Ситуация такая, что в зависимости от изменения значения

cout.precision( 7 );

а также изменения

double dist( pt & p1, pt & p2 ) {
    return sqrt( ( double )( p1.x - p2.x ) * ( p1.x - p2.x ) +
            ( p1.y - p2.y ) * ( p1.y - p2.y) );
}

на

long double dist( pt & p1, pt & p2 ) {
    return sqrt( ( long double )( p1.x - p2.x ) * ( p1.x - p2.x ) +
            ( p1.y - p2.y ) * ( p1.y - p2.y) );
}

происходит варьирование теста, на котором падает мое решение. От 4-го до 8-го. Вполне может быть, что ошибка в реализации функции convex_hull, хотя я её в упор не вижу. smile У кого-нибудь есть идея с какой точностью нужно выводить ответ или как посчитать верный ответ? Или же может у меня ошибка в другом вообще, а я не туда смотрю...

Заранее спасибо за помощь.

2

Re: Convex Hull

Мне показалось, или программа действительно не удалит три точки, лежащие на одной прямой? По условию должна.

Ну и, конечно, странно, что просто double не хватает. Хотя, когда координаты такие огромные, и long double может не хватить, но вряд ли авторы задачи закладывали в неё такой изврат smile

3

Re: Convex Hull

Программа удаляет 3 точки лежащие на одной прямой, т.к.:

while( up.size() > 1 && ccw( up[ up.size() - 2 ], up[ up.size() - 1 ], v[ vec[ i ] ] ) )
                up.pop_back(),
                u.pop_back();

и

while( down.size() > 1 && cw( down[ down.size() - 2 ], down[ down.size() - 1 ], v[ vec[ i ] ] ) )
                down.pop_back(),
                d.pop_back();

В то время, как в:

int cw( pt & p1, pt & p2, pt & p3 ) {
    return (
            ( p1.y + p2.y ) * ( p2.x - p1.x ) + 
            ( p2.y + p3.y ) * ( p3.x - p2.x ) +
            ( p1.y + p3.y ) * ( p1.x - p3.x )
            ) >= 0;
}
int ccw( pt & p1, pt & p2, pt & p3 ) {
    return (
            ( p1.y + p2.y ) * ( p2.x - p1.x ) + 
            ( p2.y + p3.y ) * ( p3.x - p2.x ) +
            ( p1.y + p3.y ) * ( p1.x - p3.x )
            ) <= 0;
}

проверяется равенство 0. Или я не совсем верно понял:

Мне показалось, или программа действительно не удалит три точки, лежащие на одной прямой?

По поводу точности - была идея переписать на Java с BigDecimal, но всё же должно же быть решение на С++, которое проходит. smile

4

Re: Convex Hull

Ну в общем на глаз ошибки не видно, а то, что прога уже на 4 тесте падала по точности - говорит о том, что и long double может не спасти smile Так что лучше пробуй на Джаве.

5

Re: Convex Hull

Спасибо за совет. Попробую на Java с BigDecimal. О результате отпишусь smile