QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#725609#5426. Drain the Water TankhelloccclWA 1ms5836kbC++201.4kb2024-11-08 19:03:482024-11-08 19:03:48

Judging History

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

  • [2024-11-08 19:03:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5836kb
  • [2024-11-08 19:03:48]
  • 提交

answer

//ALL IN
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define int long long
#define double long double
const int N=2e6+7;
const int mod=1e9+7;
const int inf=4e18;
mt19937 rnd(time(0));
clock_t start,over;// start=clock(); last=(final-over)*1.0/1000
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0',ch=getchar();}return x*f;}
inline void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');return;}
struct node {
	int x;
	int y;
};
struct node a[N];
int pre[N];
int n,k;
int cross(int x1,int y1,int x2,int y2){
	return x1*y2-x2*y1;
}
void solve(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i].x>>a[i].y;
	}
	int pre=0,next=1,ans=0;
	for(int i=0;i<n;i++){
		while(a[i].y==a[next].y){
			next=(next+1)%n;
		}
		pre=(i-1+n)%n;
		if(a[i].y<a[pre].y&&a[i].y<a[next].y){
			if(a[i].y==a[(i+1)%n].y){
				continue;
				
			}
			if(cross(a[i].x-a[pre].x,a[i].y-a[pre].y,a[next].x-a[i].x,a[next].y-a[i].y)>0){
				ans++;
			}
			else if(a[i].x<a[(i+1)%n].x){
				ans++;
			}
		}
	}
	cout<<ans<<"\n";
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	//cin>>_;
	while(_--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5836kb

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: -100
Wrong Answer
time: 1ms
memory: 5724kb

input:

8
4 4
0 4
0 2
1 2
2 2
2 0
3 0
4 0

output:

0

result:

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