QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#105994#5420. Inscryption0xyz#WA 2ms3352kbC++141.0kb2023-05-16 10:24:202023-05-16 10:24:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-16 10:24:22]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3352kb
  • [2023-05-16 10:24:20]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,fa[2010],c[2010],ans=0,p[2010];
struct pt{int x,y;}a[2010];
inline bool cross(pt p,pt q,pt r){
	int x_1,y_1,x_2,y_2;
	x_1=p.x-q.x;y_1=p.y-q.y;
	x_2=r.x-q.x;y_2=r.y-q.y;
	return x_1*y_2<=x_2*y_1;
}
inline int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void merge(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx!=fy)fa[fx]=fy;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	memset(p,-1,sizeof(p));
	for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
	a[0]=a[n];a[n+1]=a[1];
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=2;i<=n;i++)
		if(a[i].y==a[i-1].y)merge(i,i-1);
	if(a[1].y==a[n].y)merge(1,n);
	for(int i=1;i<=n;i++)
		if(a[i].y<=a[i-1].y&&a[i].y<=a[i+1].y&&cross(a[i-1],a[i],a[i+1]))c[find(i)]=1;
	for(int i=1;i<=n;i++)
		if(a[i].y>a[i+1].y)p[find(i)]=i+1;
		else if(a[i].y>a[i-1].y)p[find(i)]=i-1;
	for(int i=1;i<=n;i++)
		if(i==find(i)&&p[i]<0)ans+=c[i];
	cout<<ans<<'\n';
	return 0;
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3352kb

input:

6
7
1 1 1 -1 1 1 -1
4
1 0 -1 0
4
0 -1 -1 0
1
0
2
0 0
1
-1

output:

2

result:

wrong answer 1st lines differ - expected: '3 2', found: '2'