QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#341028#7730. Convex Checkercrsfaa#WA 1ms3640kbC++141.3kb2024-02-29 15:05:512024-02-29 15:05:53

Judging History

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

  • [2024-07-04 19:27:17]
  • hack成功,自动添加数据
  • (/hack/727)
  • [2024-07-04 19:17:30]
  • hack成功,自动添加数据
  • (/hack/726)
  • [2024-02-29 15:05:53]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3640kb
  • [2024-02-29 15:05:51]
  • 提交

answer

#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
using Yukinoshita Yukino;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
const int mxn=2e5+5;
using ll=long long;
struct vec
{
	int x,y;
	friend bool operator <(const vec &x,const vec &y)
	{
		return x.x==y.x?x.y<y.y:x.x<y.x;
	}
	friend ll operator *(const vec &x,const vec &y)
	{
		return 1ll*x.x*y.y-1ll*x.y*y.x;
	}
	friend vec operator -(const vec &x,const vec &y)
	{
		return vec({x.x-y.x,x.y-y.y});
	}
}a[mxn],b[mxn];
ll check(vec a,vec b,vec c)
{
	return (b-a)*(c-a);
}
double dis(vec a,vec b)
{
	return sqrt(1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y));
}
int main()
{
	int n=read(),i,top=0;
	for(i=1;i<=n;i++)
		a[i].x=read(),a[i].y=read();
	sort(a+1,a+1+n);
	ll sum=0;
	for(i=2;i<n;i++)
		sum+=abs(check(a[1],a[i],a[i+1]));
	for(i=1;i<=n;i++)
	{
		for(;top>1&&check(b[top-1],b[top],a[i])<=0;top--);
		b[++top]=a[i];
	}
	int tp=top;
	for(i=n-1;i;i--)
	{
		for(;top>tp&&check(b[top-1],b[top],a[i])<=0;top--);
		b[++top]=a[i];
	}
	for(i=2;i<n;i++)
		sum-=abs(check(b[1],b[i],b[i+1]));
	if(top==n&&!sum) cout<<"Yes";
	else cout<<"No";
//	printf("%.8f",s);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3640kb

input:

3
0 0
1 0
0 1

output:

No

result:

wrong answer expected YES, found NO