QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#352084#7730. Convex Checker_SheepsheepWA 0ms3928kbC++176.9kb2024-03-12 20:32:262024-03-12 20:32:27

Judging History

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

  • [2024-07-04 19:27:17]
  • hack成功,自动添加数据
  • (/hack/727)
  • [2024-07-04 19:17:30]
  • hack成功,自动添加数据
  • (/hack/726)
  • [2024-03-12 20:32:27]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3928kb
  • [2024-03-12 20:32:26]
  • 提交

answer

#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-7 ;
const LD box = 1e7 ;
int sgn( LD x )
{
    return x > eps ? 1 : ( x < -eps ? -1 : 0 ) ;
}
struct point
{
    LD x , y , polar_angle;
    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 ;
    }

    friend ostream & operator << ( ostream &out , point &a )
    {
        out << "(" << a.x << "," << a.y << ")" ;
        return out ;
    }
    friend istream & operator >> ( istream &in , point &a )
    {
        in >> a.x >> a.y ;
        return in ;
    }
    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 ;
}
bool turn_left( const line &a , const line &b , const line &c )
{
    // bc?????????a???
    return turn_left( a.s , a.t , line_intersect(b,c) ) ;
}
int point_quadrant( const point &a )
{
    if( sgn( a.x ) >= 0 && sgn( a.y ) >= 0 ) return 1 ;
    else if( sgn(a.x) < 0 && sgn( a.y ) >= 0 ) return 2 ;
    else if( sgn(a.x) < 0 && sgn( a.y ) < 0 ) return 3 ;
    else return 4 ;

}
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 ;
}
int half( const point &a ) //???????
{
    return a.y > 0 || ( a.y == 0 && a.x > 0 ? 1 : 0 );
}
bool is_para( const line &a , const line &b ) //?????
{
    return sgn( det(a.t-a.s,b.t-b.s) ) == 0 ;
}
bool cmp( const line &a , const line &b )
{
    // (0,0) is org
    int sign = half( a.t-a.s ) - half( b.t-b.s ) ; //????????
    int dir = sgn( det(a.t-a.s,b.t-b.s) ) ; //????

    if( sign == 0 && dir == 0 ) return sgn( det(a.t-a.s , b.t-a.s) ) < 0 ; //??????
    else return sign ? sign > 0 : dir > 0 ;
    //???????????
    //??????????
}
vector<point> hpi( vector<line> A , LD DX , LD DY )
{
    int siz_a = A.size() ;
    vector<line>h ;
    for( int i = 0 ; i < siz_a ; i ++ ) h.push_back( A[i] ) ;

    h.push_back( {{DX,DY} , {0,DY}} ) ;
    h.push_back( {{0,DY} , {0,0}} ) ;
    h.push_back( {{0,0} , {DX,0}} ) ;
    h.push_back( {{DX,0} , {DX,DY}} ) ;
    sort( h.begin() , h.end() , cmp ) ;

    vector<line> q( h.size()+10 ) ;
    int l = 0 , r = -1 ;
    for( auto &i : h )
    {
        while( l<r && !turn_left(i,q[r-1],q[r]) ) --r ;
        while( l<r && !turn_left(i,q[l],q[l+1]) ) ++l ;
        if( l <= r && is_para(i,q[r]) ) continue ;
        q[++r] = i ;
    }
    while( r-l>1 && !turn_left(q[l],q[r-1],q[r]) ) --r ;
    while( r-l>1 && !turn_left(q[r],q[l],q[l+1]) ) ++l ;

    if( r-l < 2 ) return {} ;
    vector<point> ret(r-l+1) ;
    for( int i = l ; i <= r ; i ++ )
        ret[i-l] = line_intersect( q[i] , q[i==r?l:i+1] ) ;
    return ret ;
}
bool on_box( point a )
{
    if( sgn(a.x-box) == 0 || sgn(a.y-box) == 0 ) return 1 ;
    return 0;
}
bool is_open( vector<point>ret )
{
    if( ret.size() <= 2 )
    for( auto &u : ret ) if( on_box(u) ) return 1 ;
    return 0 ;
}
void solve()
{
    int n ; cin >> n ;
    vector<point>a(n) ;
    for( int i = 0 ; i < n ; i ++ )
    {
        cin >> a[i] ;
        if( a[i].x == a[0].x )
        {
            if( a[i].y < a[0].y ) swap( a[i] , a[0] ) ;
        }
        else if( a[i].x < a[0].x ) swap( a[i] , a[0] ) ;
    }

    //???(a^b)??b??
    sort( a.begin()+1 , a.end() , [&]( point x , point y ){
            if( sgn(x.y-a[0].y) != sgn(y.y-a[0].y) ) return x.y < y.y ;
            return sgn(det( x-a[0] , y-a[0] )) > 0 ;
          } );

    bool ok = 1 ;
    for( int i = 1 ; i < n ; i ++ )
    {
        if( !turn_left( a[i-1] , a[i] , a[(i+1)%n] ) ) ok = 0 ;
    }

    if( ok ) cout << "Yes\n" ;
    else cout << "No\n" ;

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

詳細信息

Test #1:

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

input:

3
0 0
1 0
0 1

output:

Yes

result:

ok answer is YES

Test #2:

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

input:

4
0 0
0 1
1 1
1 0

output:

Yes

result:

ok answer is YES

Test #3:

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

input:

4
0 0
0 3
1 2
1 1

output:

Yes

result:

ok answer is YES

Test #4:

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

input:

3
0 0
0 0
0 0

output:

No

result:

ok answer is NO

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3924kb

input:

5
1 0
4 1
0 1
2 0
3 2

output:

Yes

result:

wrong answer expected NO, found YES