QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#315301#7906. Almost Convex_SheepsheepWA 517ms4184kbC++176.3kb2024-01-27 10:37:282024-01-27 10:37:28

Judging History

你现在查看的是最新测评结果

  • [2024-01-27 10:37:28]
  • 评测
  • 测评结果:WA
  • 用时:517ms
  • 内存:4184kb
  • [2024-01-27 10:37:28]
  • 提交

answer

//pbds
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int inf = 1e8 ;
const int N = 3e6+9 ;
typedef long double LD ;
const LD eps = 1e-6 ;
int sgn( LD x )
{
    return x > eps ? 1 : ( x < -eps ? -1 : 0 ) ;
}
struct point
{
    LD x , y ;
    point operator + (const point &a) const
    {
        return{ x+a.x , y+a.y } ;
    }
    point operator - (const point &a) const
    {
        return{ x-a.x , y-a.y } ;
    }
    point operator * (const LD &a) const
    {
        return{ x*a , y*a } ;
    }
    point operator / (const LD &a) const
    {
        return{ x/a , y/a } ;
    }

    friend bool operator == ( const point &a , const point &b )
    {
        return sgn(a.x-b.x) == 0 && sgn(a.y-b.y) == 0 ;
    }
    int idx , hull_rank ;
};
struct line
{
    point s , t ;
    friend bool operator == ( const line &a , const line &b )
    {
        return (a.s==b.s&&a.t==b.t)||(a.s==b.t&&a.t==b.s) ;
    }
};
LD sqr( LD x )
{
    return x*x ;
}
LD mo( point x )
{
    return sqrtl( sqr(x.x) + sqr(x.y) ) ;
}
LD dis( const point &a , const point &b )
{
    return sqrtl( sqr(a.x-b.x) + sqr(a.y-b.y) ) ;
}
LD dot( const point &a , const point &b )
{
    return a.x*b.x+a.y*b.y;
}
LD det( const point &a , const point &b )
{
    // + : b ? a ??????
    return a.x*b.y-b.x*a.y ;
}
bool point_on_segment( const point &a , const line &l )
{
    if( l.s == l.t )
    {
        return a == l.s ;
    }
    return sgn( det(l.s-a,a-l.t) ) == 0 && sgn( dot(l.s-a,l.t-a) ) <= 0 ;
}
bool two_side( const point &a , const point &b , const line &c )
{
    // ???????
    return sgn( det(a-c.s,c.t-c.s) ) * sgn( det(b-c.s,c.t-c.s) ) < 0 ;
}
bool segment_inter_judge( const line &a , const line &b )
{
    bool ok = 0 ;
    ok |= point_on_segment( b.s , a ) ;
    ok |= point_on_segment( b.t , a ) ;
    ok |= point_on_segment( a.s , b ) ;
    ok |= point_on_segment( a.t , b ) ;
    ok |= ( two_side(a.s,a.t,b)&&two_side(b.s,b.t,a) ) ;
    return ok ;
}
bool ray_inter_judge( const line &a , const line &b )
{
    //??????????
    return sgn( det( a.t-a.s , b.t-b.s ) ) == 0 ? 0 : 1 ;
}
LD point_to_line( const point &p , const line &l )
{
    return fabs( det(l.t-l.s,p-l.s) )/dis(l.s,l.t) ;
}
LD point_to_segment( const point &p , const line &l )
{
    if( l.s == l.t ) return dis( p , l.s ) ;
    if( sgn( dot(l.s-p,l.t-l.s) )*sgn( dot(l.t-p,l.t-l.s) ) <= 0 ) return point_to_line(p,l) ;
    else return min( dis(p,l.s) , dis(p,l.t) ) ;
}
LD arg( const line &a , const line &b )
{
    LD res = dot( a.t-a.s , b.t-b.s ) ;
    res /= mo( a.t-a.s ) ;
    res /= mo( b.t-b.s ) ;
    return acos( res ) ;
}
point line_intersect( const line &a , const line &b )
{
    LD u = det( a.t-a.s,b.s-a.s ) ;
    LD v = -det( a.t-a.s , b.t-a.s ) ;
    return ( b.s*v + b.t*u )/(v+u) ;
}
bool turn_left( const point &a , const point &b , const point &c )
{
    // a ???????ac????ab??????????
    return sgn( det( b-a , c-a ) ) > 0 ;
}
int point_quadrant( const point &a )
{
    if( sgn( a.x ) >= 0 && sgn( a.y ) >= 0 ) return 1 ;

}
vector<point> convex_hull( vector<point> a )
{
    vector<point>ret ;
    int a_size = a.size() , ret_size = 0 ;
    if( a_size <= 2 ) return a ;
    sort( a.begin() , a.end() , []( point x , point y ){ return x.x == y.x ? x.y < y.y : x.x < y.x ; } )  ;
    for( int i = 0 ; i < a_size ; i ++ )
    {
        while( ret_size > 1 && !turn_left( ret[ret_size-2] , ret[ret_size-1] , a[i] ) )
        {
            ret.pop_back() ; ret_size -- ;
        }
        ret.push_back( a[i] ) ; ret_size ++ ;
    }
    int fix = ret_size ;
    for( int i = a_size-2 ; i >= 0 ; i -- )
    {
        while( ret_size > fix && !turn_left( ret[ret_size-2] , ret[ret_size-1] , a[i] ) )
        {
            ret.pop_back() ; ret_size -- ;
        }
        ret.push_back( a[i] ) ; ret_size ++ ;
    }
    ret.pop_back() ; ret_size -- ;

    return ret ;
}
void solve()
{
    int n ; cin >> n ;
    vector<point> a(n) ;
    for( int i = 0 ; i < n ; i ++ )
    {
        cin >> a[i].x >> a[i].y ; a[i].idx = i ;
    }

    vector<point> b = convex_hull( a ) ;
    int m = b.size() ;
    vector<int> rnk(n,-1) ;
    for( int i = 0 ; i < m ; i ++ ) rnk[ b[i].idx ] = i ;

    vector<point> c ;
    for( int i = 0 ; i < n ; i ++ )
    {
        a[ i ].hull_rank = rnk[ a[i].idx ] ;
        if( a[i].hull_rank == -1 ) c.push_back( a[i] ) ;
    }

    long long ans = 1 ;
    for( point u : c )
    {
        vector<point>A; for( int i = 0 ; i < n ; i ++ ) if( a[i].idx != u.idx ) A.push_back(a[i]) ;
        vector<double>ATAN2(n) ;
        for( int i = 0 ; i < n-1 ; i ++ )
        {
            ATAN2[A[i].idx] = atan2( A[i].y-u.y, A[i].x-u.x)  ;
        }
        sort( A.begin() , A.end() , [&]( point x , point y )
            {
                //???
                if(sgn(ATAN2[x.idx] - ATAN2[y.idx]) == 0) //dcmp?????????0???
                return x.x < y.x ;
                return ATAN2[x.idx] < ATAN2[y.idx] ;
            }
        ) ;

        //cout << "u.id=" << u.idx+1 << "\n" ;

        //for( int i = 0 ; i < n-1 ; i ++ ) cout << A[i].idx+1 << " " ; cout << "\n" ;
        //for( int i = 0 ; i < n-1 ; i ++ ) cout << A[i].hull_rank+1 << " " ; cout << "\n" ;

        for( int i = 0 ; i < n-2 ; i ++ )
        {
            if( A[i].hull_rank != -1 && A[i+1].hull_rank != -1 )
            {
                if( ( A[i].hull_rank == 0 && A[i+1].hull_rank == m-1 ) ||
                    ( A[i].hull_rank == m-1 && A[i+1].hull_rank == 0 ) ||
                    ( ((int)abs(A[i].hull_rank - A[i+1].hull_rank)) == 1 )
                   )
                   {
                       ans ++ ;
                       //cout << "     " << A[i].idx+1 << " " << A[i+1].idx+1 << "\n" ;
                   }
            }
        }
        if( A[0].hull_rank != -1 && A[n-2].hull_rank != -1 )
        {
            if( ( A[0].hull_rank == 0 && A[n-2].hull_rank == m-1 ) ||
                ( A[0].hull_rank == m-1 && A[n-2].hull_rank == 0 ) ||
                ( ((int)abs(A[0].hull_rank - A[n-2].hull_rank)) == 1 )
                )
                {
                    ans ++ ;
                    //cout << "     " << A[0].idx+1 << " " << A[n-2].idx+1 << "\n" ;
                }
        }

    }

    cout << ans << "\n" ;

}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int tt = 1 ; //cin >> tt ;
    while( tt-- ) solve() ;
    return 0 ;
}
/*
3
0 0 0 1 0 0 1 0
0 0 1 0 0 1 0 -1
1 1 1 2 0 0 0 3
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3956kb

input:

7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

5
4 0
0 0
2 1
3 3
3 1

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3960kb

input:

6
0 0
3 0
3 2
0 2
1 1
2 1

output:

7

result:

ok 1 number(s): "7"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 510ms
memory: 4088kb

input:

2000
86166 617851
383354 -277127
844986 386868
-577988 453392
-341125 -386775
-543914 -210860
-429613 606701
-343534 893727
841399 339305
446761 -327040
-218558 -907983
787284 361823
950395 287044
-351577 -843823
-198755 138512
-306560 -483261
-487474 -857400
885637 -240518
-297576 603522
-748283 33...

output:

718

result:

ok 1 number(s): "718"

Test #7:

score: 0
Accepted
time: 510ms
memory: 4084kb

input:

2000
571314 -128802
-57762 485216
-713276 485201
-385009 -844644
371507 403789
338703 -272265
-913641 438001
-792118 -481524
709494 213762
-913577 432978
-397111 709021
840950 328210
-843628 452653
-20721 126607
-107804 -338102
930109 -89787
-949115 -76479
-862141 455623
991761 94852
-635475 625573
...

output:

658

result:

ok 1 number(s): "658"

Test #8:

score: 0
Accepted
time: 512ms
memory: 4184kb

input:

2000
-510540 -289561
-602648 -189950
-403224 944455
-369582 -41334
358122 -598933
-817147 470207
-440180 -735160
-705634 61719
319062 897001
-905089 -755682
-408371 -520115
-423336 548115
-590242 835990
208155 883477
-202087 142035
-71545 411206
570690 -673204
-228451 -903435
-732876 -570271
-246755...

output:

309

result:

ok 1 number(s): "309"

Test #9:

score: 0
Accepted
time: 516ms
memory: 4120kb

input:

2000
-532115 566389
138405 49337
398814 -97324
116833 113216
381728 877609
222402 641022
109920 952381
-113880 395181
13780 -572931
-676608 605202
-74328 -503839
-207767 926500
-663270 -146303
197877 280349
275865 -663892
-630214 3286
973786 304855
-493735 841584
394901 -505975
757960 204724
-373328...

output:

239

result:

ok 1 number(s): "239"

Test #10:

score: -100
Wrong Answer
time: 517ms
memory: 4068kb

input:

2000
512636 509804
-661126 -592269
755566 -721837
-878213 441853
-236050 -89069
-181220 155656
203391 691764
940154 260513
747075 373881
620423 840991
-409624 335472
270937 -710659
-751290 -673585
250341 -193243
-250535 618887
-739996 543936
-547741 -213681
-82920 -364319
-611672 737719
930798 46731...

output:

1027

result:

wrong answer 1st numbers differ - expected: '1025', found: '1027'