QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#644999#5426. Drain the Water TanktsaiWA 0ms3916kbC++141.5kb2024-10-16 16:24:382024-10-16 16:24:40

Judging History

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

  • [2024-10-16 16:24:40]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3916kb
  • [2024-10-16 16:24:38]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
struct node{
	int x;
	int y;
}no[1000050];
//vector<node>v;
vector<int>tem;
bool check(int l,int r,int mid){
	int y1=no[mid].y-no[l].y;
	int x1=no[mid].x-no[l].x;
	int x2=no[r].x-no[l].x;
	int y2=no[r].y-no[l].y;
	return ((x1*y2-x2*y1)>0);
}
void solve(){
	int n;
	scanf("%d",&n);
	int st=0;
	for(int i=0;i<=n-1;i++){
		scanf("%d %d",&no[i].x,&no[i].y);
	}
	for(int i=0;i<n-1;i++){
		if(no[i+1].y==no[i].y){
			st++;
		}else{
			break;
		}
	}
	int l=st,mid,r;
	mid=(l+1)%n;r=(mid+1)%n;
	int cnt=0;
	while(1){
		tem.clear();
		while(no[r].y==no[mid].y){
			tem.push_back(mid);
			mid++;
			mid%=n;
			r=(mid+1)%n;	
		}
		int now=0;
		r=(mid+1)%n;
		for(auto mi:tem){
			if(no[l].y>no[mi].y&&no[r].y>no[mi].y){
				if(check(l,r,mi)){
					now++;
				}
			}
		}
		if(no[l].y>no[mid].y&&no[r].y>no[mid].y){
			if(check(l,r,mid)){
				now++;
			}
		}
		cnt+=(now>0);
		l=mid;mid++;
		mid%=n;
		r=(mid+1)%n;
		if(l==st){
			break;
		}
	}
	printf("%d",cnt);
}

int main(){
	int t=1;
//	scanf("%d",&t);
	while(t--){
		solve();
		if(t) printf("\n");
	}
	return 0;
}
/*
10
1 0
2 0
3 0
2 1
3 2
2 2
1 2
0 2
1 1
0 0
//1


6
0 0
2 0
1 1
4 1
5 0
3 4
//2

16
0 0
60 0
60 70
0 70
0 20
40 20
40 50
20 50
20 40
30 40
30 30
10 30
10 60
50 60
50 10
0 10
//2

16
2 0
3 0
3 1
5 1
5 6
0 6
0 4
1 4
1 3
2 3
2 5
3 5
3 3
4 3
4 2
2 2
//2
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3916kb

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: 3856kb

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: 0
Accepted
time: 0ms
memory: 3832kb

input:

6
0 0
2 0
1 1
4 1
5 0
3 4

output:

2

result:

ok 1 number(s): "2"

Test #5:

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

input:

8
0 0
1 0
3 -1
3 0
1 1
4 1
5 0
3 4

output:

2

result:

ok 1 number(s): "2"

Test #6:

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

input:

5
0 0
170 0
140 30
60 30
0 70

output:

1

result:

ok 1 number(s): "1"

Test #7:

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

input:

5
0 0
170 0
140 30
60 30
0 100

output:

1

result:

ok 1 number(s): "1"

Test #8:

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

input:

5
0 0
1 2
1 5
0 2
0 1

output:

1

result:

ok 1 number(s): "1"

Test #9:

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

input:

3
0 0
100 0
0 100

output:

0

result:

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