QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#243448#7730. Convex Checkertnos#WA 0ms3916kbC++141.8kb2023-11-08 11:56:142023-11-08 11:56:15

Judging History

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

  • [2024-07-04 19:27:17]
  • hack成功,自动添加数据
  • (/hack/727)
  • [2024-07-04 19:17:30]
  • hack成功,自动添加数据
  • (/hack/726)
  • [2023-11-08 11:56:15]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3916kb
  • [2023-11-08 11:56:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define double long long
struct vec
{
	double x,y;
	vec(){}
	vec(double x_,double y_)
	{
		x=x_,y=y_;
	}
	friend vec operator +(const vec &x,const vec &y)
	{
		return vec(x.x+y.x,x.y+y.y);
	}
	friend vec operator -(const vec &x,const vec &y)
	{
		return vec(x.x-y.x,x.y-y.y);
	}
	friend vec operator *(const vec &x,const double &y)
	{
		return vec(x.x*y,x.y*y);
	}
	friend double operator &(const vec &x,const vec &y)
	{
		return x.x*y.x+x.y*y.y;
	}
	friend double operator *(const vec &x,const vec &y)
	{
		return x.x*y.y-x.y*y.x;
	}
	double mol()
	{
		return sqrt(x*x+y*y);
	}
	friend bool operator <(const vec &x,const vec &y)
	{
		return x.x==y.x?x.y<y.y:x.x<y.x;
	}
	friend double check(vec a,vec b,vec c)
	{
	    return (b-a)*(c-a);
	}
	friend double dis(const vec &x,const vec &y)
	{
		return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
	}
};
struct convex_hull
{
	int n,cnt;
	vector<vec> a,s;
	convex_hull()
	{
		a.push_back({});
	}
	void insert(vec x)
	{
		a.push_back({});
		a[++n]=x;
	}
	void build()
	{
		int i,t;
//		sort(a.begin()+1,a.begin()+1+n);
		s.push_back({});
		s[0]=a[1];
		for(i=2;i<=n;i++)
		{
			while(cnt&&check(s[cnt-1],s[cnt],a[i])<0)
				cnt--,s.pop_back();
			s.push_back({});
			s[++cnt]=a[i];
		}
		t=cnt;
		for(i=n-1;i>=1;i--)
		{
			while(cnt!=t&&check(s[cnt-1],s[cnt],a[i])<0)
				cnt--,s.pop_back();
			s.push_back({});
			s[++cnt]=a[i];	
		}
	}
}t;
int main()
{
	int n,i;
	vec x;
	double ans=0;
	scanf("%d",&n);
	set<pair<int,int>> tp;
	for(i=1;i<=n;i++)
	{
		int xx,y;
		scanf("%d%d",&xx,&y);
		tp.insert({xx,y});
		x.x=xx,x.y=y,t.insert(x);
	}
	if(tp.size()<n)
	{
		puts("No");
		return 0;
	}
	t.build();
	if(t.cnt<n)
		puts("No");
	else
		puts("Yes");
		
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0 0
1 0
0 1

output:

Yes

result:

ok answer is YES

Test #2:

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

input:

4
0 0
0 1
1 1
1 0

output:

Yes

result:

ok answer is YES

Test #3:

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

input:

4
0 0
0 3
1 2
1 1

output:

Yes

result:

ok answer is YES

Test #4:

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

input:

3
0 0
0 0
0 0

output:

No

result:

ok answer is NO

Test #5:

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

input:

5
1 0
4 1
0 1
2 0
3 2

output:

Yes

result:

wrong answer expected NO, found YES