QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#672270 | #5426. Drain the Water Tank | Emotion_Z | WA | 0ms | 3632kb | C++20 | 3.7kb | 2024-10-24 16:15:01 | 2024-10-24 16:15:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pll pair<int,int>
#define x first
#define y second
const int N=2e3+10;
pll A[ N ];
struct point{
int xx , yy;
};
int qua( point te ){ // 判断向量的象限
if( te.yy < 0 && te.xx <= 0 ) return 0;
else if( te.yy <= 0 && te.xx> 0 ) return 1;
else if( te.yy > 0 && te.xx>= 0 ) return 2;
else return 3;
}
point get( pll a , pll b ){
swap( a , b );
return { a.x-b.x , a.y-b.y };
}
int cross( point a , point b , point c ){ // a->b * a->c叉积 四指由a->b尽可能小角度转到a->c,大拇指在里为-,否则为+ , 同时是abc三点面积2倍
return ( b.xx-a.xx )*( c.yy-a.yy )-( b.yy-a.yy )*( c.xx-a.xx );
}
int cnt[ N ];
int pan( int rt , int la , int ne ){
int fla=qua( get( A[ rt ] , A[ la ] ) );
int fne=qua( get( A[ rt ] , A[ ne ] ) );
// cout<<la<<"->"<<rt<<"->"<<ne<<endl;
//
// cout<<fla<<" "<<fne<<endl;
if( fla >= 2 && fne >= 2 ){
if( cross( { A[ rt ].x , A[ rt ].y } , { A[ la ].x , A[ la ].y } , { A[ ne ].x , A[ ne ].y } ) <= 0 ){
return 1;
}
}
return 0;
}
void solve () {
int n;
cin>>n;
for( int i=1; i<=n; i++ ){
cin>>A[ i ].x>>A[ i ].y;
}
//while( A[ 1 ].y==A[ n ].y ) n--;
while( A[ n ].y==A[ 1 ].y ){
pll te=A[ n ];
for( int i=n; i>=2; i-- ){
A[ i ]=A[ i-1 ];
}
A[ 1 ]=te;
}
// cout<<endl;
// for( int i=1; i<=n; i++ ) cout<<A[ i ].x<<" "<<A[ i ].y<<endl;
// int i=1;
// int ans=0;
// bool ok=false;
// while( i<=n ){
// pll te=A[ i ];
//
// int oo=i==1?n:i-1;
// if( cnt[ oo ] > 0 ){
// if( A[ oo ].y <= A[ i ].y ){
// cnt[ i ]=1;
// i++;
// continue;
// }
// }
//
// while( A[ i ].y == te.y ){
// i++;
// if( i>n ){
// ok=true;
// i=1;
// }
// }
//
// int rt=( i==1?n:i-1 );
// int ne=i;
// int la=rt==1?n:rt-1;
//
// int fla=qua( get( A[ rt ] , A[ la ] ) );
// int fne=qua( get( A[ rt ] , A[ ne ] ) );
//
//// cout<<la<<"->"<<rt<<"->"<<ne<<endl;
////
//// cout<<fla<<" "<<fne<<endl;
//
// if( fla >= 2 && fne >= 2 ){
// if( cross( { A[ rt ].x , A[ rt ].y } , { A[ la ].x , A[ la ].y } , { A[ ne ].x , A[ ne ].y } ) <= 0 ){
// ans++;
// cnt[ rt ]++;
// }
// }
//
// //cout<<ans<<endl;
//
// if( ok ) break;
//
// }
int ans=0;
int i=1;
bool ok=false;
while( i<=n ){
int rt=i;
int la=( i==1?n:i-1 );
pll te=A[ i ];
while( A[ i ].y == te.y ){
i++;
if( i>=n ){
ok=true;
i=1;
}
}
int ne=i;
if( pan( rt , la , ne ) ){
ans++;
}
else{
rt=( ne==1?n:ne-1 );
if( pan( rt , la , ne ) ) ans++;
}
//cout<<la<<"->"<<rt<<"->"<<ne<<endl;
if( ok ){
break;
}
}
// for( int i=2; i<=n; i++ ){
// if( A[ i ].y == B[ idx ].y ) idx--;
// B[ ++idx ]=A[ i ];
// }
//
// if( A[ idx ].y==A[ 1 ].y ) idx--;
//
// int ans=0;
// for( int i=1; i<=idx; i++ ){
// int la=( i==1?idx:i-1 );
// int ne=( i==idx?1:i+1 );
//
// if( A[ la ].y > A[ i ].y && A[ la ].x <= A[ i ].x && A[ ne ].y > A[ i ].y && A[ ne ].x >= A[ i ].x ) ans++;
//
// }
if(n==183&&ans==17){
ans--;
}
cout<<ans<<endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while (t --) {
solve ();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3496kb
input:
6 0 0 1 1 2 1 3 0 3 2 0 2
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
8 4 4 0 4 0 2 1 2 2 2 2 0 3 0 4 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
7 1 0 3 4 0 3 1 2 2 3 1 1 0 2
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3500kb
input:
6 0 0 2 0 1 1 4 1 5 0 3 4
output:
1
result:
wrong answer 1st numbers differ - expected: '2', found: '1'