QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#315301 | #7906. Almost Convex | _Sheepsheep | WA | 517ms | 4184kb | C++17 | 6.3kb | 2024-01-27 10:37:28 | 2024-01-27 10:37:28 |
Judging History
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'