QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#672270#5426. Drain the Water TankEmotion_ZWA 0ms3632kbC++203.7kb2024-10-24 16:15:012024-10-24 16:15:02

Judging History

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

  • [2024-10-24 16:15:02]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3632kb
  • [2024-10-24 16:15:01]
  • 提交

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'